CRC16(lzhに記録されるもの)を求める

[みけCAT]

gcc4.7.0(Dev-C++ 5.2.0.3)です。
今、いろいろなハッシュ値を求めるソフトを作っています。
CRC16を求めるプログラムを作りたいのですが、どうすればいいかわかりません。
できればテーブルを埋め込まず、実行時に計算してテーブルを作りたいです。

このCRC32を求めるプログラムは成功しました。

コード:

#include "crc32.h"

static unsigned int CRC32table[256];
static int inited=0;
static unsigned int crc;

void crc32init(void) {
	if(!inited) {
		int n;
		for(n=0;n<256;n++) {
			unsigned int c=(unsigned int)n;
			int k;
			for(k=0;k<8;k++) {
				if(c & 1) {
					c=0xEDB88320u ^ (c>>1);
				} else {
					c>>=1;
				}
			}
			CRC32table[n]=c;
		}
		inited=1;
	}
	crc=0xFFFFFFFFu;
}

void crc32addData(const void* data,int dataSize) {
	unsigned char* now=(unsigned char*)data;
	int i;
	for(i=0;i<dataSize;i++) {
		crc=CRC32table[(crc ^ (*now))&0xFF]^(crc>>8);
		now++;
	}
}

void crc32finish(unsigned char* crc32,const void* data,int dataSize) {
	crc32addData(data,dataSize);
	crc=~crc;
	crc32[0]=(crc>>24)&0xff;
	crc32[1]=(crc>>16)&0xff;
	crc32[2]=(crc>>8)&0xff;
	crc32[3]=crc&0xff;
}

実際に計算する部分はこうなっています。

コード:

	fp=fopen(argv[1],"rb");
	if(fp==NULL) {
		fprintf(stderr,"File open error\n");
		return 1;
	}
	initFunc();
	while(!feof(fp)) {
		readSize=fread(buffer,1,BUFFER_SIZE,fp);
		if(readSize<BUFFER_SIZE) {
			finishFunc(theHash,buffer,readSize);
		} else {
			addDataFunc(buffer,BUFFER_SIZE);
		}
	}

CRC32の場合、
initFuncにはcrc32init、addDataFuncはcrc32addData、finishFuncはcrc32finishのポインタが入っています。

これと同じような感じでCRC16を求めたいのですが、どうすればいいのでしょうか？
今書いたコードをこれです。CRC32のコードをちょっとだけ書き換えただけであり、うまくいきません。

コード:

#include "crc16.h"

static unsigned short CRC16table[256];
static int inited=0;
static unsigned short crc;

void crc16init(void) {
	if(!inited) {
		int n;
		for(n=0;n<256;n++) {
			unsigned short c=(unsigned short)n;
			int k;
			for(k=0;k<8;k++) {
				if(c & 1) {
					c=0xA001 ^ (c>>1);
				} else {
					c>>=1;
				}
			}
			CRC16table[n]=c;
		}
		inited=1;
	}
	crc=0xFFFF;
}

void crc16addData(const void* data,int dataSize) {
	unsigned char* now=(unsigned char*)data;
	int i;
	for(i=0;i<dataSize;i++) {
		crc=CRC16table[(crc ^ (*now))&0xFF]^(crc>>8);
		now++;
	}
}

void crc16finish(unsigned char* crc16,const void* data,int dataSize) {
	crc16addData(data,dataSize);
	crc=~crc;
	crc16[0]=(crc>>8)&0xff;
	crc16[1]=crc&0xff;
}

例えば、abcという3バイトのデータの場合、lzhに記録されているCRC16の値は9738(16進)です。

また、この質問ではlzhで記録されるCRC16を求めたいのですが、
同じabcというデータのCRC16をgizmoで求めるとa8b6となりました。
また、hira様のcrc.dllで求めると、61DAとなりました。
CRC16はどれを信じればいいのでしょうか？
lzhは+Lhaca Version1.24で作成しました。

メモとしてWikipediaへのリンクを置いておきます。

[みけCAT]

ハッシュ値関連で、Adler32についての質問もお願いします。
「abc」のAdler32を求めたとき、
http://hash.online-convert.com/adler32-generator
では024D0127となるのですが、HashTab 3.0.0を使うと27014D02となっています。
どちらが正しいのでしょうか？
メモとしてWikipediaへのリンクを置いておきます。
コードはこちらです。

コード:

#include "adler32.h"

#define MOD_BY 65521

unsigned int A,B;

void adler32init(void) {
	A=1;
	B=0;
}

void adler32addData(const void* data,int dataSize) {
	unsigned char* now=(unsigned char*)data;
	int i;
	for(i=0;i<dataSize;i++) {
		A+=(*now);
		if(A>=MOD_BY)A-=MOD_BY;
		B+=A;
		if(B>=MOD_BY)B-=MOD_BY;
		now++;
	}
}

void adler32finish(unsigned char* adler32,const void* data,int dataSize) {
	adler32addData(data,dataSize);
	adler32[0]=(B>>8)&0xff;
	adler32[1]=B&0xff;
	adler32[2]=(A>>8)&0xff;
	adler32[3]=A&0xff;
}

追記
Hashtab v4.0.0でも024D0127になりました。

[ピヨ]

Lha for UNIXのソース (http://sourceforge.jp/projects/lha/scm/ ... rc/crcio.c) を見てみました。

コード:

#include <stdio.h>
#include <limits.h> /* UCHAR_MAX, CHAR_BIT */

unsigned int crctable[UCHAR_MAX + 1];
#define UPDATE_CRC(crc, c) \
 (crctable[((crc) ^ (c)) & 0xFF] ^ ((crc) >> CHAR_BIT))
#define CRCPOLY         0xA001      /* CRC-16 (x^16+x^15+x^2+1) */

void
make_crctable( /* void */ )
{
    unsigned int    i, j, r;

    for (i = 0; i <= UCHAR_MAX; i++) {
        r = i;
        for (j = 0; j < CHAR_BIT; j++)
            if (r & 1)
                r = (r >> 1) ^ CRCPOLY;
            else
                r >>= 1;
        crctable[i] = r;
    }
}

unsigned int
calccrc(crc, p, n)
    unsigned int crc;
    unsigned char  *p;
    unsigned int    n;
{
    while (n-- > 0)
        crc = UPDATE_CRC(crc, *p++);
    return crc;
}

main()
{
    make_crctable();
    printf("%x\n", calccrc(0, "abc", 3));
    return 0;
}

実行すると

コード:

% cc -fno-builtin crc.c && ./a.out
9738

が得られます。


> CRC16はどれを信じればいいのでしょうか？

Wikipediaにも書いてありますが、生成多項式の種類、初期値、出力xorの値などによっていくつかのバリエーションがあります。 上の例だと、CRCPOLY = 0xa001, 初期値 = 0xffff, 出力xor = 0xffffで0xa8b6が、CRCPOLY = 0x8408, 初期値 = 0xffff, 出力xor = 0で0x61daが得られます。

[みけCAT]

ありがとうございます。
このコードで、いくつかのファイルに対してlzhと同じCRC16が出力されることを確認しました。

コード:

#include "crc16.h"

static unsigned short CRC16table[256];
static int inited=0;
static unsigned short crc;

void crc16init(void) {
	if(!inited) {
		int n;
		for(n=0;n<256;n++) {
			unsigned short c=(unsigned short)n;
			int k;
			for(k=0;k<8;k++) {
				if(c & 1) {
					c=0xA001 ^ (c>>1);
				} else {
					c>>=1;
				}
			}
			CRC16table[n]=c;
		}
		inited=1;
	}
	crc=0;
}

void crc16addData(const void* data,int dataSize) {
	unsigned char* now=(unsigned char*)data;
	int i;
	for(i=0;i<dataSize;i++) {
		crc=CRC16table[(crc ^ (*now))&0xFF]^(crc>>8);
		now++;
	}
}

void crc16finish(unsigned char* crc16,const void* data,int dataSize) {
	crc16addData(data,dataSize);
	crc16[0]=(crc>>8)&0xff;
	crc16[1]=crc&0xff;
}

Adler32については、Wikipediaに

これらのバイトはネットワークオーダー（ビッグエンディアン）で格納され、B が最上位バイト側に位置する。

とあるので、新しいHashtabを信じます。