php crc 16アルゴリズムの実装

crc(サイクル冗長検査)は、データの完全性と正確性を検査するためによく用いられるアルゴリズムであり、ネットワーク伝送検査、圧縮アルゴリズムなどによく用いられる.簡単に言えば、crcは検査対象文字列を非常に大きな整数として、特定の数で除算し、得られた残数はcrc検査値であり、除算演算を行う場合にすぎない.バイナリ数の加減には模二演算、すなわち異或演算を採用し、詳細なcrc紹介は以下を参照してください.https://www.lammertbies.nl/comm/info/crc-calculation.html
crcチェックは、除数のバイナリビット数に基づいて、通常crc-8、crc-16、crc-32などがあり、同時にこの除数の選択、および初期値、結果異或値、入力がビットビットで反転するかどうか、出力がビットビットで反転するかどうか、同じビット幅のcrcアルゴリズムはまた様々な異なる実装に分けられる.例えば、
CRC-16/CITT:除数は0 x 1021に選択し、初期値は0、最終結果はフロントエイリアスまたは0を出力し、入力したバイトごとにビットビットで反転し、結果は最終エイリアスまたはフロントエイリアスでビットで反転する
CRC-16/MODBUS:除数0 x 8005、初期値0 xffffとして選択され、最終結果はフロントエイリアスまたは0を出力し、入力されたバイトごとにビットビットで反転し、結果は最終エイリアスまたは前にビットで反転する.
php原生はcrc 32法を提供したが、crc 16法は提供されず、効率の要求が高くない場合、phpを使用してcrc 16アルゴリズムを実現することができる.

/**
 *               eg: 65 (01000001) --> 130(10000010)
 * @param $char
 * @return $char
 */
function reverseChar($char) {
    $byte = ord($char);
    $tmp = 0;
    for ($i = 0; $i < 8; ++$i) {
        if ($byte & (1 << $i)) {
            $tmp |= (1 << (7 - $i));
        }
    }
    return chr($tmp);
}

/**
 *              eg: 'AB'(01000001 01000010)  --> '\x42\x82'(01000010 10000010)
 * @param $str
 */
function reverseString($str) {
    $m = 0;
    $n = strlen($str) - 1;
    while ($m <= $n) {
        if ($m == $n) {
            $str{$m} = reverseChar($str{$m});
            break;
        }
        $ord1 = reverseChar($str{$m});
        $ord2 = reverseChar($str{$n});
        $str{$m} = $ord2;
        $str{$n} = $ord1;
        $m++;
        $n--;
    }
    return $str;
}

/**
 * @param string $str       
 * @param int $polynomial    
 * @param int $initValue    
 * @param int $xOrValue          
 * @param bool $inputReverse                  
 * @param bool $outputReverse             
 * @return int
 */
function crc16($str, $polynomial, $initValue, $xOrValue, $inputReverse = false, $outputReverse = false) {
    $crc = $initValue;

    for ($i = 0; $i < strlen($str); $i++) {
        if ($inputReverse) {
            //               
            $c = ord(reverseChar($str{$i}));
        } else {
            $c = ord($str{$i});
        }
        $crc ^= ($c << 8);
        for ($j = 0; $j < 8; ++$j) {
            if ($crc & 0x8000) {
                $crc = (($crc << 1) & 0xffff) ^ $polynomial;
            } else {
                $crc = ($crc << 1) & 0xffff;
            }
        }
    }
    if ($outputReverse) {
        //        ，               
        $ret = pack('cc', $crc & 0xff, ($crc >> 8) & 0xff);
        //                
        $ret = reverseString($ret);
        //                
        $arr = unpack('vshort', $ret);
        $crc = $arr['short'];
    }
    return $crc ^ $xOrValue;
}

以下に、一般的なcrc 16アルゴリズムの実装を示します.基本的には、いくつかの大工場で採用されているか、または○○プロトコルで使用されているもので、Webサイトを使用することができます.http://www.ip33.com/crc.htmlオンライン計算

/*        crc16   */

// CRC-16/IBM
printf("%x
", crc16('1234567890', 0x8005, 0, 0, true, true));

// CRC-16/MAXIM
printf("%x
", crc16('1234567890', 0x8005, 0, 0xffff, true, true));

// CRC-16/USB
printf("%x
", crc16('1234567890', 0x8005, 0xffff, 0xffff, true, true));

// CRC-16/MODBUS
printf("%x
", crc16('1234567890', 0x8005, 0xffff, 0, true, true));

// CRC-16/CCITT
printf("%x
", crc16('1234567890', 0x1021, 0, 0, true, true));

// CRC-16/CCITT-FALSE
printf("%x
", crc16('1234567890', 0x1021, 0xffff, 0, false, false));

// CRC-16/X25
printf("%x
", crc16('1234567890', 0x1021, 0xffff, 0xffff, true, true));

// CRC-16/XMODEM
printf("%x
", crc16('1234567890', 0x1021, 0, 0, false, false));

// CRC-16/DNP
printf("%x
", crc16('1234567890', 0x3d65, 0, 0xffff, true, true));

以上の実行結果:

c57a
3a85
3df5
c20a
286b
3218
4b13
d321
bc1b

 
対比として,phpで自分のcrc 32関数を実現し,phpが持つcrc 32関数の計算結果と比較する.
 

function php_crc32($str) {
    $polynomial = 0x04c11db7;
    $crc = 0xffffffff;
    for ($i = 0; $i < strlen($str); $i++) {
        $c = ord(reverseChar($str{$i}));
        $crc ^= ($c << 24);
        for ($j = 0; $j < 8; $j++) {
            if ($crc & 0x80000000) {
                $crc = (($crc << 1) & 0xffffffff) ^ $polynomial;
            } else {
                $crc = ($crc << 1) & 0xffffffff;
            }
        }
    }
    $ret = pack('cccc', $crc & 0xff, ($crc >> 8) & 0xff, ($crc >> 16) & 0xff, ($crc >> 24) & 0xff);
    $ret = reverseString($ret);
    $arr = unpack('Vret', $ret);
    $ret = $arr['ret'] ^ 0xffffffff;
    return $ret;
}

var_dump(php_crc32('1234567890') === crc32('1234567890'));
var_dump(php_crc32('php         ') === crc32('php         '));

実行結果:

bool(true)
bool(true)

単純な比較での計算効率:

";

$start2 = microtime(true);
echo 'crc32: ' . crc32($str) . PHP_EOL;
echo 'crc32    ：' . (microtime(true) - $start2) . PHP_EOL;

結果:

string length: 1048576
my crc32:3171559529
my crc32    ：5.8124451637268
----------------------------------------------------------------------
crc32: 3171559529
crc32    ：0.0083820819854736

結果は同じですが、パフォーマンスの差は3桁です.
以上の実装は基本的にビット演算であるが,比較的長い文字列に対しては演算量が大きいが,実際のcrc実装では事前に生成された配列を用いて直接テーブルを調べるのが一般的で,大量の計算を減らすことができ,興味があれば自分で検討してみることができる.
That's all