crc.c

00001 /* libFLAC - Free Lossless Audio Codec library
00002  * Copyright (C) 2000-2009  Josh Coalson
00003  * Copyright (C) 2011-2014  Xiph.Org Foundation
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  * notice, this list of conditions and the following disclaimer.
00011  *
00012  * - Redistributions in binary form must reproduce the above copyright
00013  * notice, this list of conditions and the following disclaimer in the
00014  * documentation and/or other materials provided with the distribution.
00015  *
00016  * - Neither the name of the Xiph.org Foundation nor the names of its
00017  * contributors may be used to endorse or promote products derived from
00018  * this software without specific prior written permission.
00019  *
00020  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00021  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00022  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00023  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
00024  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00025  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00026  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00027  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00028  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00029  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00030  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00031  */
00032 
00033 #ifdef HAVE_CONFIG_H
00034 #  include <config.h>
00035 #endif
00036 
00037 #include "private/crc.h"
00038 
00039 /* CRC-8, poly = x^8 + x^2 + x^1 + x^0, init = 0 */
00040 
00041 FLAC__byte const FLAC__crc8_table[256] = {
00042     0x00, 0x07, 0x0E, 0x09, 0x1C, 0x1B, 0x12, 0x15,
00043     0x38, 0x3F, 0x36, 0x31, 0x24, 0x23, 0x2A, 0x2D,
00044     0x70, 0x77, 0x7E, 0x79, 0x6C, 0x6B, 0x62, 0x65,
00045     0x48, 0x4F, 0x46, 0x41, 0x54, 0x53, 0x5A, 0x5D,
00046     0xE0, 0xE7, 0xEE, 0xE9, 0xFC, 0xFB, 0xF2, 0xF5,
00047     0xD8, 0xDF, 0xD6, 0xD1, 0xC4, 0xC3, 0xCA, 0xCD,
00048     0x90, 0x97, 0x9E, 0x99, 0x8C, 0x8B, 0x82, 0x85,
00049     0xA8, 0xAF, 0xA6, 0xA1, 0xB4, 0xB3, 0xBA, 0xBD,
00050     0xC7, 0xC0, 0xC9, 0xCE, 0xDB, 0xDC, 0xD5, 0xD2,
00051     0xFF, 0xF8, 0xF1, 0xF6, 0xE3, 0xE4, 0xED, 0xEA,
00052     0xB7, 0xB0, 0xB9, 0xBE, 0xAB, 0xAC, 0xA5, 0xA2,
00053     0x8F, 0x88, 0x81, 0x86, 0x93, 0x94, 0x9D, 0x9A,
00054     0x27, 0x20, 0x29, 0x2E, 0x3B, 0x3C, 0x35, 0x32,
00055     0x1F, 0x18, 0x11, 0x16, 0x03, 0x04, 0x0D, 0x0A,
00056     0x57, 0x50, 0x59, 0x5E, 0x4B, 0x4C, 0x45, 0x42,
00057     0x6F, 0x68, 0x61, 0x66, 0x73, 0x74, 0x7D, 0x7A,
00058     0x89, 0x8E, 0x87, 0x80, 0x95, 0x92, 0x9B, 0x9C,
00059     0xB1, 0xB6, 0xBF, 0xB8, 0xAD, 0xAA, 0xA3, 0xA4,
00060     0xF9, 0xFE, 0xF7, 0xF0, 0xE5, 0xE2, 0xEB, 0xEC,
00061     0xC1, 0xC6, 0xCF, 0xC8, 0xDD, 0xDA, 0xD3, 0xD4,
00062     0x69, 0x6E, 0x67, 0x60, 0x75, 0x72, 0x7B, 0x7C,
00063     0x51, 0x56, 0x5F, 0x58, 0x4D, 0x4A, 0x43, 0x44,
00064     0x19, 0x1E, 0x17, 0x10, 0x05, 0x02, 0x0B, 0x0C,
00065     0x21, 0x26, 0x2F, 0x28, 0x3D, 0x3A, 0x33, 0x34,
00066     0x4E, 0x49, 0x40, 0x47, 0x52, 0x55, 0x5C, 0x5B,
00067     0x76, 0x71, 0x78, 0x7F, 0x6A, 0x6D, 0x64, 0x63,
00068     0x3E, 0x39, 0x30, 0x37, 0x22, 0x25, 0x2C, 0x2B,
00069     0x06, 0x01, 0x08, 0x0F, 0x1A, 0x1D, 0x14, 0x13,
00070     0xAE, 0xA9, 0xA0, 0xA7, 0xB2, 0xB5, 0xBC, 0xBB,
00071     0x96, 0x91, 0x98, 0x9F, 0x8A, 0x8D, 0x84, 0x83,
00072     0xDE, 0xD9, 0xD0, 0xD7, 0xC2, 0xC5, 0xCC, 0xCB,
00073     0xE6, 0xE1, 0xE8, 0xEF, 0xFA, 0xFD, 0xF4, 0xF3
00074 };
00075 
00076 /* CRC-16, poly = x^16 + x^15 + x^2 + x^0, init = 0 */
00077 
00078 unsigned const FLAC__crc16_table[256] = {
00079     0x0000,  0x8005,  0x800f,  0x000a,  0x801b,  0x001e,  0x0014,  0x8011,
00080     0x8033,  0x0036,  0x003c,  0x8039,  0x0028,  0x802d,  0x8027,  0x0022,
00081     0x8063,  0x0066,  0x006c,  0x8069,  0x0078,  0x807d,  0x8077,  0x0072,
00082     0x0050,  0x8055,  0x805f,  0x005a,  0x804b,  0x004e,  0x0044,  0x8041,
00083     0x80c3,  0x00c6,  0x00cc,  0x80c9,  0x00d8,  0x80dd,  0x80d7,  0x00d2,
00084     0x00f0,  0x80f5,  0x80ff,  0x00fa,  0x80eb,  0x00ee,  0x00e4,  0x80e1,
00085     0x00a0,  0x80a5,  0x80af,  0x00aa,  0x80bb,  0x00be,  0x00b4,  0x80b1,
00086     0x8093,  0x0096,  0x009c,  0x8099,  0x0088,  0x808d,  0x8087,  0x0082,
00087     0x8183,  0x0186,  0x018c,  0x8189,  0x0198,  0x819d,  0x8197,  0x0192,
00088     0x01b0,  0x81b5,  0x81bf,  0x01ba,  0x81ab,  0x01ae,  0x01a4,  0x81a1,
00089     0x01e0,  0x81e5,  0x81ef,  0x01ea,  0x81fb,  0x01fe,  0x01f4,  0x81f1,
00090     0x81d3,  0x01d6,  0x01dc,  0x81d9,  0x01c8,  0x81cd,  0x81c7,  0x01c2,
00091     0x0140,  0x8145,  0x814f,  0x014a,  0x815b,  0x015e,  0x0154,  0x8151,
00092     0x8173,  0x0176,  0x017c,  0x8179,  0x0168,  0x816d,  0x8167,  0x0162,
00093     0x8123,  0x0126,  0x012c,  0x8129,  0x0138,  0x813d,  0x8137,  0x0132,
00094     0x0110,  0x8115,  0x811f,  0x011a,  0x810b,  0x010e,  0x0104,  0x8101,
00095     0x8303,  0x0306,  0x030c,  0x8309,  0x0318,  0x831d,  0x8317,  0x0312,
00096     0x0330,  0x8335,  0x833f,  0x033a,  0x832b,  0x032e,  0x0324,  0x8321,
00097     0x0360,  0x8365,  0x836f,  0x036a,  0x837b,  0x037e,  0x0374,  0x8371,
00098     0x8353,  0x0356,  0x035c,  0x8359,  0x0348,  0x834d,  0x8347,  0x0342,
00099     0x03c0,  0x83c5,  0x83cf,  0x03ca,  0x83db,  0x03de,  0x03d4,  0x83d1,
00100     0x83f3,  0x03f6,  0x03fc,  0x83f9,  0x03e8,  0x83ed,  0x83e7,  0x03e2,
00101     0x83a3,  0x03a6,  0x03ac,  0x83a9,  0x03b8,  0x83bd,  0x83b7,  0x03b2,
00102     0x0390,  0x8395,  0x839f,  0x039a,  0x838b,  0x038e,  0x0384,  0x8381,
00103     0x0280,  0x8285,  0x828f,  0x028a,  0x829b,  0x029e,  0x0294,  0x8291,
00104     0x82b3,  0x02b6,  0x02bc,  0x82b9,  0x02a8,  0x82ad,  0x82a7,  0x02a2,
00105     0x82e3,  0x02e6,  0x02ec,  0x82e9,  0x02f8,  0x82fd,  0x82f7,  0x02f2,
00106     0x02d0,  0x82d5,  0x82df,  0x02da,  0x82cb,  0x02ce,  0x02c4,  0x82c1,
00107     0x8243,  0x0246,  0x024c,  0x8249,  0x0258,  0x825d,  0x8257,  0x0252,
00108     0x0270,  0x8275,  0x827f,  0x027a,  0x826b,  0x026e,  0x0264,  0x8261,
00109     0x0220,  0x8225,  0x822f,  0x022a,  0x823b,  0x023e,  0x0234,  0x8231,
00110     0x8213,  0x0216,  0x021c,  0x8219,  0x0208,  0x820d,  0x8207,  0x0202
00111 };
00112 
00113 
00114 void FLAC__crc8_update(const FLAC__byte data, FLAC__uint8 *crc)
00115 {
00116     *crc = FLAC__crc8_table[*crc ^ data];
00117 }
00118 
00119 void FLAC__crc8_update_block(const FLAC__byte *data, unsigned len, FLAC__uint8 *crc)
00120 {
00121     while(len--)
00122         *crc = FLAC__crc8_table[*crc ^ *data++];
00123 }
00124 
00125 FLAC__uint8 FLAC__crc8(const FLAC__byte *data, unsigned len)
00126 {
00127     FLAC__uint8 crc = 0;
00128 
00129     while(len--)
00130         crc = FLAC__crc8_table[crc ^ *data++];
00131 
00132     return crc;
00133 }
00134 
00135 unsigned FLAC__crc16(const FLAC__byte *data, unsigned len)
00136 {
00137     unsigned crc = 0;
00138 
00139     while(len--)
00140         crc = ((crc<<8) ^ FLAC__crc16_table[(crc>>8) ^ *data++]) & 0xffff;
00141 
00142     return crc;
00143 }