<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html><head><title>CRC Equations</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<script type="text/javascript">
// bit reversal
function bitrev(data, bits) {
var r = 0
for (var j = 0; j < bits; j++)
r = (r << 1) | ((data >>> j) & 1)
return r
}
// does data_len rounds of crc calcuation including book-keeping
function crc(poly_coeff, poly_deg, sreg, data, data_len) {
for (var i = 0; i < poly_deg; i++) {
data[i] = 0
sreg[i] = 1 << i
}
for (var i = data_len; i-- > 0; ) {
var c = sreg.pop()
sreg.unshift(0)
var d = data.pop()
data.unshift(0)
d ^= 1 << i
for (var j = 0; j < poly_deg; j++)
if ((poly_coeff & (1 << j)) != 0) {
sreg[j] ^= c
data[j] ^= d
}
}
}
function solve(data_len, poly_deg, poly_coeff, rev, minimal, simplify) {
// this is the actual equations calculation
var sreg = [] // bits used from the shift register itself
var data = [] // bits used from input data
crc(poly_coeff, poly_deg, sreg, data, data_len)
// this modified one is later used to isolate the first term
var sreg_mask = []
var data_mask = []
crc(poly_coeff ^ 1, poly_deg, sreg_mask, data_mask, data_len)
// this is the input-independent term
var sreg_zero = []
var data_zero = []
crc(0, poly_deg, sreg_zero, data_zero, data_len)
// isolate term corresponding to first bit
if (!minimal)
for (var i = 0; i < poly_deg; i++) {
sreg[i] ^= sreg_mask[i]
data[i] ^= data_mask[i]
}
// fold out some simple terms
var exor = []
if (simplify) {
var dist = poly_deg - data_len
for (i = 0; i < poly_deg; i++) {
exor[i] = (sreg[i] >>> dist) & data[i]
sreg[i] ^= exor[i] << dist
data[i] ^= exor[i]
}
}
// reflect all bits everywhere
if (rev) {
sreg.reverse()
data.reverse()
exor.reverse()
sreg_zero.reverse()
for (i = 0; i < poly_deg; i++) {
sreg[i] = bitrev(sreg[i], poly_deg)
data[i] = bitrev(data[i], data_len)
exor[i] = bitrev(exor[i], data_len)
sreg_zero[i] = bitrev(sreg_zero[i], poly_deg)
}
}
// this formats the unshifted first term (or all terms if minimal is set)
var line = []
var term = []
var width = 0
var tabs = [[sreg, "c"], [exor, (rev || data_len == poly_deg) ? "e" : "s"], [data, "d"]]
if (!minimal)
tabs.unshift([sreg_zero, "c"])
for (i = 0; i < poly_deg; i++) {
var s = ""
line[i] = ""
for (var k in tabs) {
for (var j = poly_deg; j-- > 0; )
if ((tabs[k][0][i] & (1 << j)) != 0) {
s += tabs[k][1] + j
if (j < 10 && poly_deg >= 10)
s += " "
s += " + "
}
if (tabs[k][0] === sreg_zero) {
while (s.length < 7)
s += " "
line[i] = s
s = ""
}
}
term[i] = s
width = Math.max(width, term[i].length)
}
// add an appropriately shifted term for every 1 coeff in the poly
if (minimal) poly_coeff = 1
for (i = 0; i < poly_deg; i++)
if ((poly_coeff & (1 << i)) != 0)
for (j = 0; j < poly_deg; j++) {
var idx = j + (rev ? i : -i)
s = (idx >= 0 && idx < poly_deg) ? term[idx] : ""
while (s.length < width + 2)
s += " "
line[j] += s
}
// assemble all lines into single string
s = ""
for (i in line) {
s += "r" + i
if (i < 10 && poly_deg >= 10)
s += " "
s += " = " + line[i].replace(/[+ ]+$/, "").replace(/^$/, "0") + "\r\n"
}
return s
}
function tohex(x) {
return "0x" + (x >>> 0).toString(16) // unsigned
}
function update() {
var data_len = parseInt(document.form.data_len.value)
var poly_deg = parseInt(document.form.poly_deg.value)
var poly_coeff = parseInt(document.form.poly_coeff.value)
var minimal = document.form.minimal.checked
var simplify = document.form.simplify.checked
if (document.form.rev.checked)
poly_coeff = bitrev(poly_coeff, poly_deg)
var poly = "x^" + poly_deg
for (var i = poly_deg - 1; i > 0; i--)
if ((poly_coeff & (1 << i)) != 0)
poly += " + x^" + i
if ((poly_coeff & 1) != 0)
poly += " + 1"
document.getElementById("result").firstChild.data =
"polynomial: " + poly + "\r\n" +
"poly coeffs normal (MSBF): " + tohex(poly_coeff) + "\r\n" +
solve(data_len, poly_deg, poly_coeff, false, minimal, simplify) + "\r\n\r\n" +
"polynomial: " + poly + "\r\n" +
"poly coeffs reverse (LSBF): " + tohex(bitrev(poly_coeff, poly_deg)) + "\r\n" +
solve(data_len, poly_deg, poly_coeff, true, minimal, simplify)
}
window.onload = update
</script>
</head><body>
<form name="form" action="">
<pre>input bits: <input name="data_len" value="8">
poly degree: <input name="poly_deg" value="16">
poly coeffs: <input name="poly_coeff" value="0x1021"> <input type="checkbox" name="rev" onclick="update()"> reverse
<input type="checkbox" name="minimal" onclick="update()"> minimize number of terms <input type="checkbox"
name="simplify" onclick="update()" checked> simplify
<input type="button" value="update" onclick='update()'></pre></form><pre id="result"> </pre>
</body></html>
