| 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

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; Git is not a CDN; Mining of Massive Data Sets; Rachel Kaadzi Ghansah; How great republics meet their end; Raspberry, Strawberry and Banana Jam; Interesting Dead Areas of Math; Later Taste; For Sale; Death By Bean; It's Good!; Tomato Chutney v2; Time ATAC MX 2 Pedals - First Impressions; Online Chilean Crafts; Intellectual Variety; Taste + Texture; Time Invariance and Gauge Symmetry; Jodorowsky; Tomato Chutney; Analysis of Support for Trump; Indian SF; TP-Link TL-WR841N DNS TCP Bug; TP-Link TL-WR841N as Wireless Bridge; Sending Email On Time; Maybe run a command; Sterile Neutrinos; Strawberry and Banana Jam; The Best Of All Possible Worlds; Kenzaburo Oe: The Changeling; Peach Jam; Taste Test; Strawberry and Raspberry Jam; flac to mp3 on OpenSuse 42.1; Also, Sebald; Kenzaburo Oe Interview; Otake (Kitani Minoru) move Black 121; Is free speech in British universities under threat?; I am actually good at computers; Was This Mansplaining?; WebFaction / LetsEncrypt / General Disappointment; Sensible Philosophy of Science; George Ellis; Misplaced Intuition and Online Communities; More Reading About Japan; Visibilty / Public Comments / Domestic Violence; Ferias de Santiago; More (Clearly Deliberate); Deleted Obit Post; And then a 50 yo male posts this...; We Have Both Kinds Of Contributors; Free Springer Books; Books on Religion; Books on Linguistics; Palestinan Electronica; Books In Anthropology; Taylor Expansions of Spacetime; Info on Juniper; Efficient Stream Processing; The Moral Character of Crypto; Hearing Aid Info; Small Success With Go!; Re: Quick message - This link is broken; Adding Reverb To The Echo Chamber; Sox Audio Tools

© 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