memcache.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* The contents of this file are subject to the Netscape Public
* License Version 1.1 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at http://www.mozilla.org/NPL/
*
* Software distributed under the License is distributed on an "AS
* IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
* implied. See the License for the specific language governing
* rights and limitations under the License.
*
* The Original Code is Mozilla Communicator client code, released
* March 31, 1998.
*
* The Initial Developer of the Original Code is Netscape
* Communications Corporation. Portions created by Netscape are
* Copyright (C) 1998-1999 Netscape Communications Corporation. All
* Rights Reserved.
*
* Contributor(s):
*/
/*
*
* memcache.c - routines that implement an in-memory cache.
*
* To Do: 1) ber_dup_ext().
* 2) referrals and reference?
*/
#include <assert.h>
#include "ldap-int.h"
/*
* Extra size allocated to BerElement.
*/
#define EXTRA_SIZE 1024
/* Mode constants for function memcache_access() */
#define MEMCACHE_ACCESS_ADD 0
#define MEMCACHE_ACCESS_APPEND 1
#define MEMCACHE_ACCESS_APPEND_LAST 2
#define MEMCACHE_ACCESS_FIND 3
#define MEMCACHE_ACCESS_DELETE 4
#define MEMCACHE_ACCESS_DELETE_ALL 5
#define MEMCACHE_ACCESS_UPDATE 6
#define MEMCACHE_ACCESS_FLUSH 7
#define MEMCACHE_ACCESS_FLUSH_ALL 8
#define MEMCACHE_ACCESS_FLUSH_LRU 9
/* Mode constants for function memcache_adj_size */
#define MEMCACHE_SIZE_DEDUCT 0
#define MEMCACHE_SIZE_ADD 1
#define MEMCACHE_SIZE_ENTRIES 1
#define MEMCACHE_SIZE_NON_ENTRIES 2
/* Size used for calculation if given size of cache is 0 */
/* Index into different list structure */
#define LIST_TTL 0
#define LIST_LRU 1
#define LIST_TMP 2
#define LIST_TOTAL 3
static char *emptyStr = "";
/* Macros to make code more readable */
#define NSLDAPI_STR_NONNULL( s ) ( (s) ? (s) : emptyStr )
/* Macros dealing with mutex */
#define LDAP_MEMCACHE_MUTEX_LOCK( c ) \
if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_lock ) { \
}
#define LDAP_MEMCACHE_MUTEX_UNLOCK( c ) \
if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_unlock ) { \
}
#define LDAP_MEMCACHE_MUTEX_ALLOC( c ) \
((c) && ((c)->ldmemc_lock_fns).ltf_mutex_alloc ? \
#define LDAP_MEMCACHE_MUTEX_FREE( c ) \
if ( (c) && ((c)->ldmemc_lock_fns).ltf_mutex_free ) { \
}
/* Macros used for triming unnecessary spaces in a basedn */
#define NSLDAPI_IS_SPACE( c ) \
(((c) == ' ') || ((c) == '\t') || ((c) == '\n'))
#define NSLDAPI_IS_SEPARATER( c ) \
((c) == ',')
/* Hash table callback function pointer definition */
/* Structure of a node in a hash table */
typedef struct HashTableNode_struct {
void *pData;
/* Structure of a hash table */
typedef struct HashTable_struct {
int size;
} HashTable;
/* Structure uniquely identifies a search request */
typedef struct ldapmemcacheReqId_struct {
int ldmemcrid_msgid;
/* Structure representing a ldap handle associated to memcache */
typedef struct ldapmemcacheld_struct {
struct ldapmemcacheld_struct *ldmemcl_next;
/* Structure representing header of a search result */
typedef struct ldapmemcacheRes_struct {
char *ldmemcr_basedn;
unsigned long ldmemcr_crc_key;
unsigned long ldmemcr_resSize;
unsigned long ldmemcr_timestamp;
/* Structure for memcache statistics */
typedef struct ldapmemcacheStats_struct {
unsigned long ldmemcstat_tries;
unsigned long ldmemcstat_hits;
/* Structure of a memcache object */
struct ldapmemcache {
unsigned long ldmemc_ttl;
unsigned long ldmemc_size;
unsigned long ldmemc_size_used;
unsigned long ldmemc_size_entries;
char **ldmemc_basedns;
void *ldmemc_lock;
struct ldap_thread_fns ldmemc_lock_fns;
};
/* Function prototypes */
static void memcache_trim_basedn_spaces(char *basedn);
int usageFlags, int bAdd);
unsigned long curTime);
int index);
unsigned long size);
int index);
const char *basedn);
#if 0 /* function not used */
#endif /* 0 */
#ifdef LDAP_DEBUG
#endif /* LDAP_DEBUG */
static int htable_calculate_size(int sizelimit);
/* Create a memcache object. */
int
LDAPMemCache **cachep )
{
unsigned long total_size = 0;
return( LDAP_PARAM_ERROR );
}
sizeof(LDAPMemCache))) == NULL) {
return ( LDAP_NO_MEMORY );
}
total_size += sizeof(LDAPMemCache);
/* Non-zero default size needed for calculating size of hash tables */
if (thread_fns) {
sizeof(struct ldap_thread_fns));
} else {
sizeof(struct ldap_thread_fns));
}
/* Cache basedns */
int i;
for (i = 0; baseDNs[i]; i++) {
;
}
sizeof(char*));
return ( LDAP_NO_MEMORY );
}
total_size += (i + 1) * sizeof(char*);
for (i = 0; baseDNs[i]; i++) {
return ( LDAP_NO_MEMORY );
}
}
/* Create hash table for temporary cache */
return( LDAP_NO_MEMORY );
}
/* Create hash table for primary cache */
return( LDAP_NO_MEMORY );
}
/* See if there is enough room so far */
MEMCACHE_SIZE_ADD) != LDAP_SUCCESS) {
return( LDAP_SIZELIMIT_EXCEEDED );
}
*cachep, 0, 0 );
return( LDAP_SUCCESS );
}
/* Associates a ldap handle to a memcache object. */
int
{
int nRes = LDAP_SUCCESS;
if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) )
return( LDAP_PARAM_ERROR );
/* First dissociate handle from old cache */
LDAP_MEMCACHE_MUTEX_LOCK( c );
break;
}
if (pCur) {
if (pPrev)
else
memcache_adj_size(c, sizeof(ldapmemcacheld),
}
/* Exit if no new cache is specified */
return( LDAP_SUCCESS );
}
/* Then associate handle with new cache */
return nRes;
}
} else {
}
}
return nRes;
}
/* Retrieves memcache with which the ldap handle has been associated. */
int
{
return( LDAP_PARAM_ERROR );
}
return( LDAP_SUCCESS );
}
/*
* Function that stays inside libldap and proactively expires items from
* the given cache. This should be called from a newly created thread since
* it will not return until after ldap_memcache_destroy() is called.
*/
void
{
cache, 0, 0 );
if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
return;
}
}
/* Removes specified entries from given memcache. */
void
{
"ldap_memcache_flush( cache: 0x%x, dn: %s, scope: %d)\n",
if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
return;
}
if (!dn) {
} else {
}
}
/* Destroys the given memcache. */
void
{
int i = 0;
unsigned long size = sizeof(LDAPMemCache);
cache, 0, 0 );
if ( !NSLDAPI_VALID_MEMCACHE_POINTER( cache )) {
return;
}
/* Dissociate all ldap handes from this cache. */
}
size += i * sizeof(ldapmemcacheld);
/* Free array of basedns */
if (cache->ldmemc_basedns) {
for (i = 0; cache->ldmemc_basedns[i]; i++) {
}
size += (i + 1) * sizeof(char*);
}
/* Free hash table used for temporary cache */
if (cache->ldmemc_resTmp) {
}
/* Free hash table used for primary cache */
if (cache->ldmemc_resLookup) {
}
}
/************************* Internal API Functions ****************************/
/* Creates an integer key by applying the Cyclic Reduntency Check algorithm on
a long string formed by concatenating all the search parameters plus the
current bind DN. The key is used in the cache for looking up cached
entries. It is assumed that the CRC algorithm will generate
different integers from different byte strings. */
int
{
int nRes, i, j, i_smallest;
int len;
int defport;
char buf[50];
return( LDAP_PARAM_ERROR );
*keyp = 0;
if (!memcache_exist(ld))
return( LDAP_LOCAL_ERROR );
if (nRes != LDAP_SUCCESS)
return nRes;
return( LDAP_LOCAL_ERROR );
binddn = "";
if (attrs) {
for (i = 0; attrs[i]; i++) {
for (i_smallest = j = i; attrs[j]; j++) {
i_smallest = j;
}
if (i != i_smallest) {
}
}
} else {
len += 1;
}
return( LDAP_NO_MEMORY );
}
if (attrs) {
for (i = 0; attrs[i]; i++) {
}
} else {
}
;
}
/* CRC algorithm */
return LDAP_SUCCESS;
}
/* Searches the cache for the right cached entries, and if found, attaches
them to the given ldap handle. This function relies on locking by the
caller. */
int
{
int nRes;
"ldap_memcache_result( ld: 0x%x, msgid: %d, key: 0x%8.8lx)\n",
return( LDAP_PARAM_ERROR );
}
if (!memcache_exist(ld)) {
return( LDAP_LOCAL_ERROR );
}
/* Search the cache and append the results to ld if found */
"ldap_memcache_result: key 0x%8.8lx found in cache\n",
key, 0, 0 );
} else {
"ldap_memcache_result: key 0x%8.8lx not found in cache\n",
key, 0, 0 );
}
#ifdef LDAP_DEBUG
#endif /* LDAP_DEBUG */
return nRes;
}
/* Creates a new header in the cache so that entries arriving from the
directory server can later be cached under the header. */
int
{
int nRes;
if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) ) {
return( LDAP_PARAM_ERROR );
}
if (!memcache_exist(ld)) {
return( LDAP_LOCAL_ERROR );
}
return nRes;
}
/* Appends a chain of entries to an existing cache header. Parameter "bLast"
indicates whether there will be more entries arriving for the search in
question. */
int
{
int nRes = LDAP_SUCCESS;
return( LDAP_PARAM_ERROR );
}
if (!memcache_exist(ld)) {
return( LDAP_LOCAL_ERROR );
}
if (!bLast)
else
"ldap_memcache_append: %s result for msgid %d\n",
return nRes;
}
/* Removes partially cached results for a search as a result of calling
ldap_abandon() by the client. */
int
{
int nRes;
return( LDAP_PARAM_ERROR );
}
if (!memcache_exist(ld)) {
return( LDAP_LOCAL_ERROR );
}
return nRes;
}
/*************************** helper functions *******************************/
/* Removes extraneous spaces in a basedn so that basedns differ by only those
spaces will be treated as equal. Extraneous spaces are those that
precedes the basedn and those that follow a comma. */
/*
* XXXmcs: this is a bit too agressive... we need to deal with the fact that
* commas and spaces may be quoted, in which case it is wrong to remove them.
*/
static void
{
if (!basedn)
return;
;
}
;
}
}
}
/* Verifies whether the results of a search should be cached or not by
checking if the search's basedn falls under any of the basedns for which
the memcache is responsible. */
static int
{
int i;
return( LDAP_SUCCESS );
}
#if 1
basedn = "";
}
#else
/* XXXmcs: I do not understand this code... */
}
#endif
for (i = 0; cache->ldmemc_basedns[i]; i++) {
return( LDAP_SUCCESS );
}
}
return( LDAP_OPERATIONS_ERROR );
}
/* Calculates the length of the buffer needed to concatenate the contents of
a ldap control. */
static int
{
int len = 0, i;
if (ctrls) {
for (i = 0; ctrls[i]; i++) {
}
}
return len;
}
/* Contenates the contents of client and server controls to a buffer. */
static void
{
int i, j;
LDAPControl **ctrls;
for (j = 0; j < 2; j++) {
continue;
for (i = 0; ctrls[i]; i++) {
}
pCh += 3;
}
}
}
/* Increases or decreases the size (in bytes) the given memcache currently
uses. If the size goes over the limit, the function returns an error. */
static int
int usageFlags, int bAdd)
{
"memcache_adj_size: attempting to %s %ld %s bytes...\n",
if (bAdd) {
if ((cache->ldmemc_size > 0) &&
"memcache_adj_size: failed (size > size_entries %ld).\n",
cache->ldmemc_size_entries, 0, 0 );
return( LDAP_SIZELIMIT_EXCEEDED );
}
"memcache_adj_size: failed (LRU flush failed).\n",
0, 0, 0 );
return( LDAP_SIZELIMIT_EXCEEDED );
}
}
}
if (usageFlags & MEMCACHE_SIZE_ENTRIES)
} else {
if (usageFlags & MEMCACHE_SIZE_ENTRIES)
}
#ifdef LDAP_DEBUG
"memcache_adj_size: succeeded (new size: %ld bytes).\n",
cache->ldmemc_size_used, 0, 0 );
} else {
"memcache_adj_size: succeeded (new size: %ld bytes, "
}
#endif /* LDAP_DEBUG */
return( LDAP_SUCCESS );
}
/* Searches the cache for results for a particular search identified by
parameter "key", which was generated ldap_memcache_createkey(). */
static int
{
int nRes;
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
if (nRes != LDAP_SUCCESS)
return nRes;
return( LDAP_SUCCESS );
}
/* Adds a new header into the cache as a place holder for entries
arriving later. */
static int
const char *basedn)
{
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
}
/* Appends search entries arriving from the dir server to the cache. */
static int
{
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
}
/* Same as memcache_append(), but the entries being appended are the
last from the dir server. Once all entries for a search have arrived,
the entries are moved from secondary to primary cache, and a time
stamp is given to the entries. */
static int
{
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
}
/* Removes entries from the temporary cache. */
static int
{
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
}
#if 0 /* this function is not used */
/* Wipes out everything in the temporary cache directory. */
static int
{
if (!memcache_exist(ld))
return LDAP_LOCAL_ERROR;
}
#endif /* 0 */
/* Returns TRUE or FALSE */
static int
{
}
/* Attaches cached entries to an ldap handle. */
static int
{
int nRes = LDAP_SUCCESS;
LDAPMessage **r;
if (nRes != LDAP_SUCCESS)
return nRes;
break;
if (*r)
;
}
*r = pCopy;
return nRes;
}
/* Check if main_dn is included in {dn, scope} */
static int
{
int nRes;
char **components = NULL;
char **main_components = NULL;
if (!components || !main_components) {
}
else {
int i, main_i;
break;
}
if (i >= 0 && main_i >= 0) {
}
else if (i < 0 && main_i < 0) {
if (scope != LDAP_SCOPE_ONELEVEL)
else
}
else if (main_i < 0) {
}
else {
if (scope == LDAP_SCOPE_BASE)
else if (scope == LDAP_SCOPE_SUBTREE)
else if (main_i == 0)
else
}
}
if (components)
if (main_components)
return nRes;
}
/* Dup a complete separate copy of a berelement, including the buffers
the berelement points to. */
static BerElement*
{
*pSize = 0;
if (p) {
if (p->ber_len <= EXTRA_SIZE) {
p->ber_buf = (char*)p + sizeof(BerElement);
} else {
p->ber_flags &= ~LBER_FLAG_NO_FREE_BUFFER;
}
if (p->ber_buf) {
} else {
ber_free(p, 0);
p = NULL;
*pSize = 0;
}
}
return p;
}
/* Dup a entry or a chain of entries. */
static int
{
int nRes = LDAP_SUCCESS;
unsigned long ber_size;
if (pSize)
*pSize = 0;
/* Make a copy of res */
sizeof(LDAPMessage))) == NULL) {
break;
}
if (pSize)
}
if (pSize)
*pSize = 0;
}
return nRes;
}
/************************* Cache Functions ***********************/
/* Frees a cache header. */
static int
{
if (pRes) {
unsigned long size = sizeof(ldapmemcacheRes);
if (pRes->ldmemcr_basedn) {
}
if (pRes->ldmemcr_resHead) {
}
}
return( LDAP_SUCCESS );
}
/* Detaches a cache header from the list of headers. */
static int
{
return( LDAP_SUCCESS );
}
/* Inserts a new cache header to a list of headers. */
static int
{
else
return( LDAP_SUCCESS );
}
/* Appends a chain of entries to the given cache header. */
static int
unsigned long size)
{
if (pRes->ldmemcr_resTail)
else
;
}
return( LDAP_SUCCESS );
}
#ifdef LDAP_DEBUG
static void
{
char *name;
switch( index ) {
case LIST_TTL:
name = "TTL";
break;
case LIST_LRU:
name = "LRU";
break;
case LIST_TMP:
name = "TMP";
break;
case LIST_TOTAL:
name = "TOTAL";
break;
default:
name = "unknown";
}
" key: 0x%8.8lx, ld: 0x%x, msgid: %d\n",
}
}
#endif /* LDAP_DEBUG */
/* Tells whether a cached result has expired. */
static int
unsigned long curTime)
{
if (!cache->ldmemc_ttl)
return 0;
return ((unsigned long)difftime(
cache->ldmemc_ttl);
}
/* Operates the cache in a central place. */
static int
{
int nRes = LDAP_SUCCESS;
unsigned long size = 0;
/* Add a new cache header to the cache. */
if (mode == MEMCACHE_ACCESS_ADD) {
if (nRes == LDAP_SUCCESS)
return( LDAP_ALREADY_EXISTS );
return( LDAP_NO_MEMORY );
if (nRes == LDAP_SUCCESS)
if (nRes == LDAP_SUCCESS)
else
}
/* Append entries to an existing cache header. */
else if ((mode == MEMCACHE_ACCESS_APPEND) ||
(mode == MEMCACHE_ACCESS_APPEND_LAST)) {
if (nRes != LDAP_SUCCESS)
return nRes;
if (nRes != LDAP_SUCCESS) {
return nRes;
}
if (nRes != LDAP_SUCCESS) {
return nRes;
}
if (mode == MEMCACHE_ACCESS_APPEND)
return( LDAP_SUCCESS );
(void*)&(pRes->ldmemcr_crc_key),
(void*)pRes)) == LDAP_SUCCESS) {
} else {
}
}
/* Search for cached entries for a particular search. */
else if (mode == MEMCACHE_ACCESS_FIND) {
if (nRes != LDAP_SUCCESS)
return nRes;
return( LDAP_SUCCESS );
}
}
/* Remove cached entries in the temporary cache. */
else if (mode == MEMCACHE_ACCESS_DELETE) {
(void**)&pCurRes)) == LDAP_SUCCESS) {
}
}
/* Wipe out the temporary cache. */
else if (mode == MEMCACHE_ACCESS_DELETE_ALL) {
}
/* Remove expired entries from primary cache. */
else if (mode == MEMCACHE_ACCESS_UPDATE) {
break;
}
}
/* Wipe out the primary cache. */
else if (mode == MEMCACHE_ACCESS_FLUSH_ALL) {
}
}
/* Remove cached entries in both primary and temporary cache. */
else if (mode == MEMCACHE_ACCESS_FLUSH) {
char *dnTmp;
if (cache->ldmemc_basedns) {
for (i = 0; cache->ldmemc_basedns[i]; i++) {
LDAP_SCOPE_SUBTREE) == LDAP_COMPARE_TRUE) ||
break;
}
return( LDAP_SUCCESS );
}
for (i = 0; i < 2; i++) {
LDAP_SCOPE_SUBTREE) != LDAP_COMPARE_TRUE) &&
continue;
continue;
}
}
if (!bDone)
continue;
} else {
}
}
}
}
/* Flush least recently used entries from cache */
else if (mode == MEMCACHE_ACCESS_FLUSH_LRU) {
return LDAP_NO_SUCH_OBJECT;
"memcache_access FLUSH_LRU: removing key 0x%8.8lx\n",
pRes->ldmemcr_crc_key, 0, 0 );
}
/* Unknown command */
else {
}
return nRes;
}
#ifdef LDAP_DEBUG
static void
{
unsigned long hitrate;
hitrate = 0;
} else {
}
cache->ldmemc_size_used, 0, 0 );
} else {
}
}
#endif /* LDAP_DEBUG */
/************************ Hash Table Functions *****************************/
/* Calculates size (# of entries) of hash table given the size limit for
the cache. */
static int
{
int i, j;
/* Get a prime # */
if ((size % i) == 0) {
size += 2;
i = 3;
j = size / 2;
}
}
return size;
}
/* Returns the size in bytes of the given hash table. */
static int
{
if (!pTable)
return 0;
}
/* Inserts an item into the hash table. */
static int
{
return( LDAP_OPERATIONS_ERROR );
}
/* Retrieves an item from the hash table. */
static int
{
return( LDAP_OPERATIONS_ERROR );
}
/* Performs a miscellaneous operation on a hash table entry. */
static int
{
}
return( LDAP_OPERATIONS_ERROR );
}
/* Removes an item from the hash table. */
static int
{
if (ppData)
return( LDAP_OPERATIONS_ERROR );
}
/* Removes everything in the hash table. */
static int
{
int i;
return( LDAP_SUCCESS );
}
/* Creates a new hash table. */
static int
{
return( LDAP_NO_MEMORY );
sizeof(HashTableNode));
return( LDAP_NO_MEMORY );
}
return( LDAP_SUCCESS );
}
/* Destroys a hash table. */
static int
{
return( LDAP_SUCCESS );
}
/**************** Hash table callbacks for temporary cache ****************/
/* Hash function */
static int
{
}
/* Called by hash table to insert an item. */
static int
{
break;
}
if (pCurRes) {
return( LDAP_ALREADY_EXISTS );
}
} else {
if (pPrev)
else
}
return( LDAP_SUCCESS );
}
/* Called by hash table to retrieve an item. */
static int
{
break;
}
if (!pCurRes)
return( LDAP_NO_SUCH_OBJECT );
return( LDAP_SUCCESS );
}
}
return( LDAP_NO_SUCH_OBJECT );
}
/* Called by hash table to remove an item. */
static int
{
if (ppData)
break;
}
if (!pHead)
return( LDAP_NO_SUCH_OBJECT );
break;
}
if (!pCurRes)
return( LDAP_NO_SUCH_OBJECT );
if (ppData) {
}
return( LDAP_SUCCESS );
}
if (pPrev) {
} else {
}
} else {
} else {
}
}
return( LDAP_SUCCESS );
}
/* Called by hash table to remove all cached entries associated to searches
being performed using the given ldap handle. */
static int
{
break;
}
if (!pHead)
return( LDAP_NO_SUCH_OBJECT );
if (pPrev)
else
}
return( LDAP_SUCCESS );
}
/* Called by hash table for removing all items in the table. */
static void
{
}
}
}
/********************* Hash table for primary cache ************************/
/* Hash function */
static int
{
return ((*((unsigned long*)key)) % table_size);
}
/* Called by hash table to insert an item. */
static int
{
return( LDAP_ALREADY_EXISTS );
}
return( LDAP_SUCCESS );
}
/* Called by hash table to retrieve an item. */
static int
{
return( LDAP_SUCCESS );
}
}
return( LDAP_NO_SUCH_OBJECT );
}
/* Called by hash table to remove an item. */
static int
{
if (ppData)
if (pPrev)
else
return( LDAP_SUCCESS );
}
}
if (ppData)
return( LDAP_NO_SUCH_OBJECT );
}
/* Called by hash table for removing all items in the table. */
static void
{
(void)pData;
}
}
/***************************** CRC algorithm ********************************/
/*
* Build auxiliary table for parallel byte-at-a-time CRC-32.
*/
static unsigned long crc32_table[256] = {
0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7,
0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3,
0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef,
0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb,
0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4,
0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08,
0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc,
0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050,
0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1,
0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5,
0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9,
0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd,
0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2,
0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e,
0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a,
0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676,
0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4 };
/* Initialized first time "crc32()" is called. If you prefer, you can
* statically initialize it at compile time. [Another exercise.]
*/
static unsigned long
{
char *p;
#ifdef OSF1V4D
unsigned int crc;
#else
unsigned long crc; /* FIXME: this is not 32-bits on all platforms! */
#endif /* OSF1V4D */
return (unsigned long) ~crc; /* transmit complement, per CRC-32 spec */
}