Jump to content

User talk:K5002

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Hello, K5002! Welcome to Wikipedia! Thank you for your contributions to this free encyclopedia. If you decide that you need help, check out Getting Help below, ask me on my talk page, or place {{helpme}} on your talk page and ask your question there. Please remember to sign your name on talk pages by clicking or using four tildes (~~~~); this will automatically produce your username and the date. Finally, please do your best to always fill in the edit summary field. Below are some useful links to facilitate your involvement. Happy editing! Sabri76'message 10:24, 27 July 2009 (UTC)[reply]
Getting started
Getting help
Policies and guidelines

The community

Writing articles
Miscellaneous
The Original Barnstar
Awarded for the beautifully crafted tables for LUT-less computation of CRC and references in Cyclic redundancy check. What a way to open your account, let's hope for many more edits like this! Thank you. – Regregex (talk) 19:14, 28 July 2009 (UTC)[reply]

Cool – thanks! K5002 (talk) 20:59, 30 July 2009 (UTC)[reply]

JavaScript used to create the bit-wise CRC equations

[edit]

This is some HTML/ECMAScript code to display tables as shown in computation of CRC (see the reference there about how it is working). It is not very pretty code but the output might be useful. For example, 8 bit input data with polynomial coefficients 0x80 and degree 8 shows that this is simply the computation of 8-bit parity (TRC-1/VRC-1). Or 8 bit input data with polynomial coefficients 0x01 and degree 8 is the same as LRC-8/HRC-8 (simple byte-wise exclusive-or). Save the code in a file like crc.html and load it in a browser. Feel free to use and/or improve/move it…

<!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">&nbsp;</pre>
</body></html>

K5002 (talk) 20:59, 30 July 2009 (UTC)[reply]

Code noted, thanks again. I also find it useful to plot r against e, putting an X wherever ei contributes to the value of rj. The same information appears in a visual pattern. – Regregex (talk) 23:43, 31 July 2009 (UTC)[reply]