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

Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); Get Coffee Quotes for Cat Soft LLC; [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors; [Link, Computing] Optimizatin Puzzle; [Link, Books, Politics] Orwell Prize; [Link] What the Hell Is Happening With Qatar?; [Link] Deep Learning + Virtual Tensor Machines; [Link] Scaled Composites: Largest Wingspan Ever; [Link] SCP Foundation; [Bike] Lessons From 2 Leading 2 Trailing; [Link] Veg Restaurants in Santiago; [Link] List of Contemporary Latin American Authors; [Bike] FTHR; [Link] Whoa - NSA Reduces Collection (of US Residents); [Link] Red Bull's Breitbart; [Link] Linux Threads; [Link] Punycode; [Link] Bull / Girl Statues on Wall Street; [Link] Beautiful Chair Video; Update: Lower Pressures; [Link] Neat Python Exceptions; [Link] Fix for Windows 10 to Avoid Ads; [Link] Attacks on ZRTP; [Link] UK Jazz Invasion; [Review] Cuba; [Link] Aricle on Gender Reversal of US Presidential Debate; {OpenSuse] Fix for Network Offline in Updater Applet; [Link] Parkinson's Related to Gut Flora; Farellones Bike Park; [Meta] Tags; Update: Second Ride; Schwalbe Thunder Burt 2.1 v Continental X-King 2.4; Mountain Biking in Santiago; Books on Ethics; Security Fail from Command Driven Interface; Everything Old is New Again; Interesting Take on Trump's Lies; Chutney v6; References on Entropy; Amusing "Alexa.." broadcast; The Shame of Chile's Education System; Playing mp4 gifs in Firefox on Opensuses Leap 42.2; Concurrency at Microsoft; Globalisation: Uk -> Chile; OpenSuse 42.2 and Synaptics Touch-Pads; Even; Cherry Jam; Lebanese Writer Amin Maalouf; C++ - it's the language of the future; Learning From Trump; Chinese Writer Hu Fayun; 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

© 2006-2017 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