Last active
July 18, 2022 13:13
-
-
Save bryc/5916452ad0d1ef5c39f1a3f19566d315 to your computer and use it in GitHub Desktop.
CRC
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Cyclic redundancy check (CRC-4, CRC-8, CRC-16, CRC-32) | |
| Common CRC implementation supporting wide range of configurations: | |
| http://reveng.sourceforge.net/crc-catalogue/all.htm | |
| NOTE: These common polynomials are likely suboptimal. | |
| In the future I should make a page of Koopman's best general purpose polynomials. | |
| http://github.com/bryc | |
| */ | |
| // :::::::::::::::: CRC-4/ITU :::::::::::::::: | |
| var crc4 = function(data) { | |
| var POLY = 0xC, INIT = 0, XOROUT = 0; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ data[i]; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) & 0xF; | |
| }; | |
| // :::::::::::::::: CRC-4/ITU (lookup table) :::::::::::::::: | |
| var crc4 = function(data) { | |
| var POLY = 0xC, INIT = 0, XOROUT = 0; | |
| for(var crc = 0, i = 0, table = []; i < 256; i++) { | |
| crc = i; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| table[i] = crc & 0xF; | |
| } | |
| return function(data) { | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ crc & 0xFF] ^ crc >>> 8; | |
| } | |
| return (crc ^ XOROUT) & 0xF; | |
| } | |
| }(); | |
| // :::::::::::::::: CRC-8/ITU :::::::::::::::: | |
| var crc8 = function(data) { | |
| var POLY = 0x07, INIT = 0, XOROUT = 0x55; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ data[i]; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 0x80 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) & 0xFF; | |
| }; | |
| // :::::::::::::::: CRC-8/ITU (lookup table) :::::::::::::::: | |
| var crc8 = function(data) { | |
| var POLY = 0x07, INIT = 0, XOROUT = 0x55; | |
| for(var crc = INIT, i = 0, table = []; i < 256; i++) { | |
| crc = i; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 0x80 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| table[i] = crc & 0xFF; | |
| } | |
| return function(data) { | |
| for(var crc = 0, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ crc & 0xFF] ^ crc << 8; | |
| } | |
| return (crc ^ XOROUT) & 0xFF; | |
| } | |
| }(); | |
| // :::::::::::::::: CRC-16/CCITT :::::::::::::::: | |
| var crc16 = function(data) { | |
| var POLY = 0x8408, INIT = 0, XOROUT = 0; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ data[i]; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) & 0xFFFF; | |
| }; | |
| // :::::::::::::::: CRC-16/CCITT (lookup table) :::::::::::::::: | |
| var crc16 = function(data) { | |
| var POLY = 0x8408, INIT = 0, XOROUT = 0; | |
| for(var crc = INIT, i = 0, table = []; i < 256; i++) { | |
| crc = i; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| table[i] = crc & 0xFFFF; | |
| } | |
| return function(data) { | |
| for(var crc = 0, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ crc & 0xFF] ^ crc >>> 8; | |
| } | |
| return (crc ^ XOROUT) & 0xFFFF; | |
| } | |
| }(); | |
| //:::::::::::::::: CRC-16/CCITT-FALSE :::::::::::::::: | |
| var crc16b = function(data) { | |
| var POLY = 0x1021, INIT = 0xFFFF, XOROUT = 0; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ (data[i] << 8); | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 0x8000 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) & 0xFFFF; | |
| }; | |
| //:::::::::::::::: CRC-16/CCITT-FALSE (lookup table) :::::::::::::::: | |
| var crc16b = function(data) { | |
| var POLY = 0x1021, INIT = 0xFFFF, XOROUT = 0; | |
| for(var crc = 0, i = 0, table = []; i < 256; i++) { | |
| crc = i << 8; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 0x8000 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| table[i] = crc & 0xFFFF; | |
| } | |
| return function(data) { | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ (crc >>> 8) & 0xFF] ^ crc << 8; | |
| } | |
| return (crc ^ XOROUT) & 0xFFFF; | |
| } | |
| }(); | |
| //:::::::::::::::: CRC-32 :::::::::::::::: | |
| var crc32 = function(data) { | |
| var POLY = 0xEDB88320, INIT = -1, XOROUT = -1; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ (data[i]); | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) >>> 0; | |
| }; | |
| //:::::::::::::::: CRC-32 (lookup table) :::::::::::::::: | |
| var crc32 = function(data) { | |
| var POLY = 0xEDB88320, INIT = -1, XOROUT = -1; | |
| for(var crc = 0, i = 0, table = []; i < 256; i++) { | |
| crc = i; | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 1 ? crc >>> 1 ^ POLY : crc >>> 1; | |
| } | |
| table[i] = crc >>> 0; | |
| } | |
| return function(data) { | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ crc & 0xFF] ^ crc >>> 8; | |
| } | |
| return (crc ^ XOROUT) >>> 0; | |
| } | |
| }(); | |
| //:::::::::::::::: CRC-32/BZIP2 :::::::::::::::: | |
| var crc32b = function(data) { | |
| var POLY = 0x04C11DB7, INIT = -1, XOROUT = -1; | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = crc ^ (data[i] << 24); | |
| for(var j = 0; j < 8; j++) { | |
| crc = crc & 0x80000000 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| } | |
| return (crc ^ XOROUT) >>> 0; | |
| }; | |
| //:::::::::::::::: CRC-32/BZIP2 (lookup table) :::::::::::::::: | |
| var crc32b = function(data) { | |
| var POLY = 0x04C11DB7, INIT = -1, XOROUT = -1; | |
| for(var crc = 0, i = 0, table = []; i < 256; i++) { | |
| crc = i << 16; | |
| for(var j = 0; j < 16; j++) { | |
| crc = crc & 0x80000000 ? crc << 1 ^ POLY : crc << 1; | |
| } | |
| table[i] = crc >>> 0; | |
| } | |
| return function(data) { | |
| for(var crc = INIT, i = 0; i < data.length; i++) { | |
| crc = table[data[i] ^ (crc >>> 24) & 0xFF] ^ crc << 8; | |
| } | |
| return (crc ^ XOROUT) >>> 0; | |
| } | |
| }(); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // ---- Important Links ------------------------------------------------------------------------------------- | |
| // http://reveng.sourceforge.net/crc-catalogue/all.htm | |
| // https://archive.is/Yjh32#selection-375.0-375.9 | |
| // https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations_of_cyclic_redundancy_checks | |
| // http://crppit.epfl.ch/documentation/Hash_Function/WiKi/Cyclic_redundancy_check.htm | |
| // http://www.zorc.breitbandkatze.de/crc.html | |
| // https://users.ece.cmu.edu/~koopman/crc/crc4.html | |
| // http://www.ross.net/crc/download/crc_v3.txt | |
| // http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html | |
| // just some old crc32 code for posterity | |
| var crc32 = function(data) | |
| { | |
| for(var i=256, tbl=[], crc, j; i--; tbl[i]=crc>>>0){ | |
| j=8;for(crc=i;j--;)crc=crc&1?crc>>>1^0xEDB88320:crc>>>1; | |
| } | |
| return function(str) { | |
| for(var i=0, crc=-1; i<data.length; ++i) | |
| crc=tbl[crc&255^data[i]]^crc>>>8; | |
| return crc^-1; | |
| } | |
| }(); | |
| // Older implementation | |
| var crc32 = (function(data) { | |
| var table = []; | |
| for (var i = 256, crc; i--;) { | |
| crc = i; | |
| for (var j = 8; j--;) { | |
| if(crc & 1) { | |
| crc = crc >>> 1 ^ 3988292384; | |
| } | |
| else {crc = crc >>> 1;} | |
| } | |
| table[i] = crc; | |
| } | |
| return function (data) { | |
| crc = -1; | |
| for (var i = 0; i < data.length; i++) { | |
| var ptr = crc & 255 ^ data[i]; | |
| crc = crc >>> 8 ^ table[ptr]; | |
| } | |
| crc = ((crc ^ -1) >>> 0).toString(16).toUpperCase(); | |
| return ("00000000" + crc).slice(-8); | |
| } | |
| }()); |
I got a invalid value with this function(data = 'abc', valid result:20810, but got 52380):
Then I checked it, and changeddata[i]todata.charCodeAt(i), then got the valid result.
Yes these functions take array as input, but you can swap with strings.
These are purely academic. For highly optimized implementations have a look here:
https://gist.github.com/bryc/79d1a62304773285317191f1ae5aa5b8
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I got a invalid value with this function(data = 'abc', valid result:20810, but got 52380):
var crc16b = function(data) {var POLY = 0x1021, INIT = 0xFFFF, XOROUT = 0;for(var crc = INIT, i = 0; i < data.length; i++) {crc = crc ^ (data[i] << 8);for(var j = 0; j < 8; j++) {crc = crc & 0x8000 ? crc << 1 ^ POLY : crc << 1;}}return (crc ^ XOROUT) & 0xFFFF;};Then I checked it, and changed
data[i]todata.charCodeAt(i), then got the valid result.