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 namespace algorithm {
00042 
00043 static const uint32_t crc32tab[256] = 
00044 {
00045   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
00046   0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
00047   0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
00048   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
00049   0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
00050   0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
00051   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
00052   0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
00053   0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
00054   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
00055   0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
00056   0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
00057   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
00058   0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
00059   0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
00060   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
00061   0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
00062   0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
00063   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
00064   0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
00065   0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
00066   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
00067   0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
00068   0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
00069   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
00070   0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
00071   0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
00072   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
00073   0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
00074   0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
00075   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
00076   0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
00077   0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
00078   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
00079   0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
00080   0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
00081   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
00082   0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
00083   0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
00084   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
00085   0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
00086   0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
00087   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
00088   0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
00089   0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
00090   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
00091   0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
00092   0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
00093   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
00094   0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
00095   0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
00096   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
00097   0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
00098   0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
00099   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
00100   0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
00101   0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
00102   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
00103   0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
00104   0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
00105   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
00106   0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
00107   0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
00108   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
00109 };
00110 
00111 template <class T>
00112 uint32_t crc32(T key, size_t key_length)
00113 {
00114   uint32_t crc= UINT32_MAX;
00115 
00116   for (size_t x= 0; x < key_length; x++)
00117     crc= (crc >> 8) ^ crc32tab[(crc ^ static_cast<uint8_t>(key[x])) & 0xff];
00118 
00119   return ~crc;
00120 }
00121 
00122 } /* namespace algorithm */
00123 } /* namespace drizzled */