Drizzled Public API Documentation

crc32.h
00001 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
00002  *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
00003  * Copyright (C) 1992-2007 The FreeBSD Project. All rights reserved.
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  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 
00014  * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00015  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00016  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00017  * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
00018  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00019  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00020  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00021  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00022  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00023  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00024  * SUCH DAMAGE.
00025  */
00026 
00027 /* 
00028  * The crc32 functions and data was originally written by Spencer
00029  * Garrett <srg@quick.com> and was gleaned from the PostgreSQL source
00030  * tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at
00031  * src/usr.bin/cksum/crc32.c.
00032  */
00033 
00034 #pragma once
00035 
00036 #ifdef HAVE_SYS_TYPES_H
00037 # include <sys/types.h>
00038 #endif
00039 
00040 namespace drizzled
00041 {
00042 namespace algorithm
00043 {
00044 
00045 static const uint32_t crc32tab[256] = {
00046   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
00047   0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
00048   0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
00049   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
00050   0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
00051   0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
00052   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
00053   0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
00054   0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
00055   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
00056   0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
00057   0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
00058   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
00059   0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
00060   0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
00061   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
00062   0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
00063   0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
00064   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
00065   0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
00066   0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
00067   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
00068   0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
00069   0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
00070   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
00071   0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
00072   0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
00073   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
00074   0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
00075   0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
00076   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
00077   0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
00078   0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
00079   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
00080   0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
00081   0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
00082   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
00083   0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
00084   0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
00085   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
00086   0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
00087   0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
00088   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
00089   0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
00090   0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
00091   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
00092   0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
00093   0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
00094   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
00095   0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
00096   0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
00097   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
00098   0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
00099   0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
00100   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
00101   0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
00102   0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
00103   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
00104   0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
00105   0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
00106   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
00107   0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
00108   0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
00109   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
00110 };
00111 
00112 template <class T>
00113 uint32_t crc32(T key, size_t key_length)
00114 {
00115   uint64_t x;
00116   uint32_t crc= UINT32_MAX;
00117 
00118   for (x= 0; x < key_length; x++)
00119     crc= (crc >> 8) ^ crc32tab[(crc ^ static_cast<uint8_t>(key[x])) & 0xff];
00120 
00121   return ~crc;
00122 }
00123 
00124 } /* namespace algorithm */
00125 } /* namespace drizzled */
00126