| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

Telephone System Quotes for Cat Soft LLC; Even; Cherry Jam; Lebanese Writer Amin Maalouf; Learning From Trump; Chinese Writer Hu Fayun; C++ - it's the language of the future; And; Apricot Jam; Also; Excellent Article on USA Politics; Oh Metafilter; Prejudice Against The Rurals; Also, Zizek; Trump; Why Trump Won; Doxygen + Latex on CentOS 6; SMASH - Solve 5 Biggest Problems in Physics; Good article on racism, brexit, and social divides; Grandaddy are back!; Consciousness From Max Entropy; Democrats; Harvard Will Fix Black Poverty; Modelling Bicycle Wheels; Amusing Polling Outlier; If Labour keeps telling working class people...; Populism and Choice; Books on Defeat; Enrique Ferrari - Argentine Author; Transcript of German Scientists on Learning of Hiroshima; Calvert Journal; Owen Jones on Twitter; Possible Japanese Authors; Complex American Literature; Chutney v5; Weird Componentized Virus; Interesting Argentinian Author - Antonio Di Benedetto; Useful Thread on MetaPhysics; RAND on fighting online anarchy (2001); NSA Hacked; Very Good LRB Article on Brexit; Nussbaum on Anger; Tasting; Apple + Kiwi Jam; Hit Me; Sudoku - CSP + Chaos; Recycling Electronics In Santiago; Vector Displays in OpenGL; And Anti-Aliased; OpenGL - Render via Intermediate Texture; And Garmin Connect; Using Garmin Forerunner 230 With Linux; (Beating Dead Horse) StackOverflow; Current State of Justice in China; Axiom of Determinacy; Ewww; Fee Chaos Book; Course on Differential Geometry; Okay, but...; Sparse Matrices, Deep Learning; Sounds Bad; Applebaum Rape; Tomato Chutney v4; Have to add...; Culturally Liberal and Nothing More; Weird Finite / Infinite Result; Your diamond is a beaten up mess; Maths Books; Good Bike Route from Providencia / Las Condes to Panul; Iain Pears (Author of Complex Plots); Plum Jam; Excellent; More Recently; For a moment I forgot StackOverflow sucked; A Few Weeks On...; Chilean Book Recommendations; How To Write Shared Libraries; Jenny Erpenbeck (Author); Dijkstra, Coins, Tables; Python libraries error on OpenSuse; Deserving Trump; And Smugness; McCloskey Economics Trilogy; cmocka - Mocks for C; Concept Creep (Americans); Futhark - OpenCL Language; Moved / Gone; Fan and USB issues; Burgers in Santiago; The Origin of Icosahedral Symmetry in Viruses; autoenum on PyPI; Jars Explains; Tomato Chutney v3; REST; US Elections and Gender: 24 Point Swing; PPPoE on OpenSuse Leap 42.1; SuperMicro X10SDV-TLN4F/F with Opensuse Leap 42.1; Big Data AI Could Be Very Bad Indeed....; Cornering; Postcapitalism (Paul Mason); Black Science Fiction

© 2006-2015 Andrew Cooke (site) / post authors (content).

16bit CRC Algorithms

From: andrew cooke <andrew@...>

Date: Wed, 31 Jul 2013 16:24:58 -0400

If you need to implement a 16bit CRC algorithm, this is an excellent
reference:

  http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code

If you have some data and are trying to work out what CRC was used, this
excellent tool is a huge help:

  http://www.lammertbies.nl/comm/info/crc-calculation.html

The only missing puzzle is that no-one explains the difference between
CRC-CCITT (0xffff) and XModem.  It turns out that XModem has an initial
remainder of zero.  So you could say that XModem is CRC-CCITT (0x0000).

That is the ONLY difference.  I have working code with test vectors.  God
knows what crack some people were smoking when they wrote that they are
different beasts...

What a painful, wasted afternoon.
Andrew

CRC16 Code

From: andrew cooke <andrew@...>

Date: Sat, 3 Aug 2013 15:13:39 -0400

Here's the C code.  As I noted above it's basically from
http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code but it
includes explicit values, validated via
http://www.lammertbies.nl/comm/info/crc-calculation.html


uint16_t straight_16(uint16_t value) {
    return value;
}

uint16_t reverse_16(uint16_t value) {
    uint16_t reversed = 0;
    for (int i = 0; i < 16; ++i) {
        reversed <<= 1;
        reversed |= value & 0x1;
        value >>= 1;
    }
    return reversed;
}

uint8_t straight_8(uint8_t value) {
    return value;
}

uint8_t reverse_8(uint8_t value) {
    uint8_t reversed = 0;
    for (int i = 0; i < 8; ++i) {
        reversed <<= 1;
        reversed |= value & 0x1;
        value >>= 1;
    }
    return reversed;
}

uint16_t crc16(uint8_t const *message, int nBytes,
        bit_order_8 data_order, bit_order_16 remainder_order,
        uint16_t remainder, uint16_t polynomial) {
    for (int byte = 0; byte < nBytes; ++byte) {
        remainder ^= (data_order(message[byte]) << 8);
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 0x8000) {
                remainder = (remainder << 1) ^ polynomial;
            } else {
                remainder = (remainder << 1);
            }
        }
    }
    return remainder_order(remainder);
}


uint16_t crc16ccitt(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0xffff, 0x1021);
}

uint16_t crc16ccitt_xmodem(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0x0000, 0x1021);
}

uint16_t crc16ccitt_kermit(uint8_t const *message, int nBytes) {
    uint16_t swap = crc16(message, nBytes, reverse_8, reverse_16, 0x0000, 0x1021);
    return swap << 8 | swap >> 8;
}

uint16_t crc16ccitt_1d0f(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, straight_8, straight_16, 0x1d0f, 0x1021);
}

uint16_t crc16ibm(uint8_t const *message, int nBytes) {
    return crc16(message, nBytes, reverse_8, reverse_16, 0x0000, 0x8005);
}


I've modified the code slightly to remove various private things and simplify
slightly, so it's just possible I broke something - please check before
using.  Also, remmeber that this is not as efficient as using a lookup-table
per byte (but you can generate the table from the info above).

Andrew

Missed a bit

From: andrew cooke <andrew@...>

Date: Sat, 3 Aug 2013 15:37:20 -0400

You also need this...

typedef uint16_t bit_order_16(uint16_t value);
typedef uint8_t bit_order_8(uint8_t value);

(which was hiding in a header file).

Andrew

thanks for CRC16-CCITT XMODEM

From: "Sanchez, Denis" <Denis.Sanchez@...>

Date: Thu, 5 Dec 2013 15:39:36 +0000

Hello,

Just a little mail to say thank you for your post on your blog.
I finally find the way to calculate this CRC and convert into excel macro.
I was hard to find algo for XMODEM.

Denis

Update on CRCs

From: andrew cooke <andrew@...>

Date: Sat, 5 Apr 2014 10:43:20 -0300

The last month or so I've learned a lot more about CRCs (as part of a longer
term project to understand finite fields).

Here are two references for CRCs that are better / more authoritative than
anything I could produce:

  http://www.zlib.net/crc_v3.txt
  http://reveng.sourceforge.net/crc-catalogue/

The first link above clarifies why there are two implementations for
algorithms that reverse the input bytes: one is slow but obviously correct
(just reverse each byte); the other is faster but looks very odd at first
glance (reverse the rest of the world).

According to the second link above, what I have called crc16ccitt is actually
CCITT-FALSE ("An algorithm commonly misidentified as CRC-CCITT").  See
http://reveng.sourceforge.net/crc-catalogue/16.htm for full details.

Finally, I have implemented fast versions (with tables and, where appropriate,
"reverse the world" implementations) for ALL the algorithms described in the
catalogue.  The code is written in Julia and is available at 
https://github.com/andrewcooke/CRC.jl

I hope to extend that code at some point so that it can be used as a
command-line tool for calculating CRCs (so you don't need to use julia).  But
even if you don't know julia it should be fairly easy to use in its current
state (email me at andrew@... if this is important to you and I can
give instructions).

Andrew

Comment on this post