~drizzle-trunk/drizzle/development : contents of drizzled/algorithm/crc32.h at revision 1892.1.2

~drizzle-trunk/drizzle/development : (revision 1892.1.2)

/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 * Copyright (C) 1992-2007 The FreeBSD Project. All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/* 
 * The crc32 functions and data was originally written by Spencer
 * Garrett <srg@quick.com> and was gleaned from the PostgreSQL source
 * tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at
 * src/usr.bin/cksum/crc32.c.
 */

#ifndef DRIZZLED_ALGORITHM_CRC32_H
#define DRIZZLED_ALGORITHM_CRC32_H

#ifdef HAVE_SYS_TYPES_H
# include <sys/types.h>
#endif

namespace drizzled
{
namespace algorithm
{

static const uint32_t crc32tab[256] = {
  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
  0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
  0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
  0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
  0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
  0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
  0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
  0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
  0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
  0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
  0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
  0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
  0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
  0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
  0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
  0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
  0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
  0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
  0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
  0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
  0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
  0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
  0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
  0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
  0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
  0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
  0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
  0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
  0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
  0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
  0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
  0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
  0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
  0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
  0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
};

template <class T>
uint32_t crc32(T key, size_t key_length)
{
  uint64_t x;
  uint32_t crc= UINT32_MAX;

  for (x= 0; x < key_length; x++)
    crc= (crc >> 8) ^ crc32tab[(crc ^ static_cast<uint8_t>(key[x])) & 0xff];

  return ~crc;
}

} /* namespace algorithm */
} /* namespace drizzled */

#endif /* DRIZZLED_ALGORITHM_CRC32_H */

1130.3.47 by Monty Taylor Added two more checks from cpplint. Added BSD license header for crc files.	1	/* -- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; --
	2	* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
	3	* Copyright (C) 1992-2007 The FreeBSD Project. All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
	13	*
	14	* THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	15	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	16	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	17	* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
	18	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	19	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	20	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	21	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	22	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	23	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	24	* SUCH DAMAGE.
	25	*/
	26
1143.1.1 by Jay Pipes Fix for bug#437896. Adds a non-ZLIB crc32 hash function taken from PostgreSQL/libmemcached and fixes casting problems in command_log and command_log_reader.	27	/*
	28	* The crc32 functions and data was originally written by Spencer
	29	* Garrett <srg@quick.com> and was gleaned from the PostgreSQL source
	30	* tree via the files contrib/ltree/crc32.[ch] and from FreeBSD at
	31	* src/usr.bin/cksum/crc32.c.
	32	*/
	33
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	34	#ifndef DRIZZLED_ALGORITHM_CRC32_H
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	35	#define DRIZZLED_ALGORITHM_CRC32_H
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	36
1241.9.1 by Monty Taylor Removed global.h. Fixed all the headers.	37	#ifdef HAVE_SYS_TYPES_H
	38	# include <sys/types.h>
	39	#endif
	40
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	41	namespace drizzled
	42	{
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	43	namespace algorithm
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	44	{
	45
1411.7.2 by Siddharth Prakash Singh templatizing drizzle::algorithm::crc32(), all tests passed	46	static const uint32_t crc32tab[256] = {
	47	0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
	48	0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
	49	0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
	50	0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
	51	0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
	52	0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
	53	0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
	54	0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
	55	0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
	56	0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
	57	0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
	58	0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
	59	0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
	60	0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
	61	0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
	62	0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
	63	0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
	64	0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
	65	0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
	66	0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
	67	0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
	68	0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
	69	0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
	70	0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
	71	0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
	72	0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
	73	0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
	74	0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
	75	0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
	76	0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
	77	0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
	78	0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
	79	0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
	80	0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
	81	0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
	82	0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
	83	0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
	84	0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
	85	0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
	86	0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
	87	0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
	88	0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
	89	0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
	90	0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
	91	0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
	92	0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
	93	0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
	94	0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
	95	0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
	96	0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
	97	0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
	98	0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
	99	0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
	100	0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
	101	0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
	102	0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
	103	0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
	104	0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
	105	0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
	106	0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
	107	0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
	108	0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
	109	0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
110	0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
111	};
112
1411.7.1 by Siddharth Prakash Singh branch for templatizing drizzled::algorithm::crc32()	113	template <class T>
	114	uint32_t crc32(T key, size_t key_length)
	115	{
	116	uint64_t x;
	117	uint32_t crc= UINT32_MAX;
	118
	119	for (x= 0; x < key_length; x++)
	120	crc= (crc >> 8) ^ crc32tab[(crc ^ static_cast<uint8_t>(key[x])) & 0xff];
	121
	122	return ~crc;
	123	}
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	124
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	125	} /* namespace algorithm */
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	126	} /* namespace drizzled */
	127
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	128	#endif /* DRIZZLED_ALGORITHM_CRC32_H */