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

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

/* -*- 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.
 */

#pragma once

#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 */


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
2234 by Brian Aker Mass removal of ifdef/endif in favor of pragma once.	34	#pragma once
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	35
1241.9.1 by Monty Taylor Removed global.h. Fixed all the headers.	36	#ifdef HAVE_SYS_TYPES_H
	37	# include <sys/types.h>
	38	#endif
	39
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	40	namespace drizzled
	41	{
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	42	namespace algorithm
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	43	{
	44
1411.7.2 by Siddharth Prakash Singh templatizing drizzle::algorithm::crc32(), all tests passed	45	static const uint32_t crc32tab[256] = {
	46	0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
	47	0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
	48	0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
	49	0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
	50	0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
	51	0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
	52	0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
	53	0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
	54	0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
	55	0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
	56	0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
	57	0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
	58	0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
	59	0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
	60	0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
	61	0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
	62	0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
	63	0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
	64	0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
	65	0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
	66	0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
	67	0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
	68	0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
	69	0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
	70	0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
	71	0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
	72	0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
	73	0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
	74	0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
	75	0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
	76	0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
	77	0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
	78	0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
	79	0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
	80	0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
	81	0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
	82	0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
	83	0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
	84	0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
	85	0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
	86	0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
	87	0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
	88	0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
	89	0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
	90	0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
	91	0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
	92	0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
	93	0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
	94	0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
	95	0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
	96	0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
	97	0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
	98	0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
	99	0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
	100	0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
	101	0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
	102	0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
	103	0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
	104	0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
	105	0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
	106	0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
	107	0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
	108	0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
109	0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
110	};
111
1411.7.1 by Siddharth Prakash Singh branch for templatizing drizzled::algorithm::crc32()	112	template <class T>
	113	uint32_t crc32(T key, size_t key_length)
	114	{
	115	uint64_t x;
	116	uint32_t crc= UINT32_MAX;
	117
	118	for (x= 0; x < key_length; x++)
	119	crc= (crc >> 8) ^ crc32tab[(crc ^ static_cast<uint8_t>(key[x])) & 0xff];
	120
	121	return ~crc;
	122	}
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	123
1259.6.2 by Joe Daly rename hash_algorithm to algorithm	124	} /* namespace algorithm */
1143.2.9 by Jay Pipes Merge Monty's fixes for moving crc32 function into a library.	125	} /* namespace drizzled */
	126