From ff76efc3e5e1b0e4ca3b10b7402406f619509bba Mon Sep 17 00:00:00 2001 From: Stef Walter Date: Wed, 21 Apr 2004 17:37:06 +0000 Subject: Initial Import --- common/buffer.c | 429 ++++++++++++++++++++++++++++++++++++++++++++++++++++ common/compat.c | 30 ++++ common/compat.h | 40 +++++ common/hash.c | 462 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ common/hash.h | 171 +++++++++++++++++++++ common/md5.c | 228 ++++++++++++++++++++++++++++ common/md5.h | 49 ++++++ 7 files changed, 1409 insertions(+) create mode 100644 common/buffer.c create mode 100644 common/compat.c create mode 100644 common/compat.h create mode 100644 common/hash.c create mode 100644 common/hash.h create mode 100644 common/md5.c create mode 100644 common/md5.h (limited to 'common') diff --git a/common/buffer.c b/common/buffer.c new file mode 100644 index 0000000..28cab24 --- /dev/null +++ b/common/buffer.c @@ -0,0 +1,429 @@ + +#include "usuals.h" +#include "httpauthd.h" + +#include + +/* ----------------------------------------------------------------------- + * Memory Buffer + */ + +/* + * LEGEND: + * _al: allocated + * _dt: data + * _rp: read/write point + * _pp: parse/begin point + */ + +void buffer_bump(ha_buffer_t* buf, int count) +{ + if(ha_buferr(buf)) + return; + + if(buf->_rp + count >= buf->_dt + buf->_al) + { + char* old = buf->_dt; + int alloc = buf->_al; + int diff; + + while((buf->_al + count) > alloc) + alloc *= 2; + + buf->_dt = (char*)reallocf(buf->_dt, alloc * sizeof(char)); + if(!buf->_dt) + { + buf->_al = 0; + buf->_rp = buf->_pp = NULL; + ha_messagex(LOG_CRIT, "out of memory"); + return; + } + + buf->_al = alloc; + + diff = buf->_dt - old; + buf->_rp += diff; + buf->_pp += diff; + } +} + +void ha_bufreset(ha_buffer_t* buf) +{ + if(!buf->_dt || buf->_al == 0) + { + buf->_dt = (char*)reallocf(buf->_dt, 256 * sizeof(char)); + if(!buf->_dt) + { + buf->_al = 0; + buf->_rp = buf->_pp = NULL; + ha_messagex(LOG_CRIT, "out of memory"); + return; + } + + buf->_al = 256; + } + + buf->_rp = buf->_dt; + buf->_pp = buf->_dt; +} + +void ha_bufinit(ha_buffer_t* buf) +{ + memset(buf, 0, sizeof(*buf)); + ha_bufreset(buf); +} + +void ha_buffree(ha_buffer_t* buf) +{ + if(buf->_dt) + free(buf->_dt); + + buf->_al = 0; + buf->_rp = buf->_pp = NULL; +} + +int ha_readline(int fd, ha_buffer_t* buf) +{ + int l; + + if(ha_buferr(buf)) + return 0; + + for(;;) + { + buffer_bump(buf, 1); + l = read(fd, (void*)buf->_rp, sizeof(char)); + + /* We got a character */ + if(l == 1) + { + /* Skip junky CRLFs */ + if(*(buf->_rp) == '\r') + { + *(buf->_rp) = ' '; + continue; + } + + /* End of line */ + else if(*(buf->_rp) == '\n') + { + buf->_rp++; + break; + } + + /* All other characters */ + else + { + buf->_rp++; + } + } + + /* If it's the end of file then return that */ + else if(l == 0) + return 0; + + /* Transient errors */ + else if(l == -1 && (errno == EINTR || errno == EAGAIN)) + continue; + + /* Fatal errors */ + else if(l == -1) + { + ha_message(LOG_ERR, "couldn't read data"); + return 0; + } + } + + return 1; +} + +char* ha_parseword(ha_buffer_t* buf, const char* delims) +{ + char* word = NULL; + + if(ha_buferr(buf)) + return NULL; + + /* Knock out any previous delims */ + while(buf->_pp < buf->_rp && strchr(delims, *(buf->_pp))) + buf->_pp++; + + /* If at end of buffer or end of line return null */ + if(buf->_pp == buf->_rp || *(buf->_pp) == '\n') + return NULL; + + /* We do this before we stash away a pointer */ + buffer_bump(buf, 1); + + word = buf->_pp; + + while(!strchr(delims, *(buf->_pp))) + { + buf->_pp++; + + /* At the end of the buffer */ + if(buf->_pp == buf->_rp) + { + *(buf->_rp) = 0; + buf->_rp++; + break; + } + + /* At the end of a line */ + else if(*(buf->_pp) == '\n') + break; + } + + /* Now null terminate what we found */ + *(buf->_pp) = 0; + buf->_pp++; + + /* We don't return empty strings */ + if(word[0] == 0) + return NULL; + + return word; +} + +char* ha_parseline(ha_buffer_t* buf, int trim) +{ + char* t; + char* line = NULL; + + if(ha_buferr(buf)) + return NULL; + + if(trim) + { + /* Knock out any previous whitespace */ + while(buf->_pp < buf->_rp && isblank(*(buf->_pp))) + buf->_pp++; + } + + if(buf->_pp == buf->_rp) + return NULL; + + /* We do this before we stash away a pointer */ + buffer_bump(buf, 1); + + line = buf->_pp; + + t = (char*)memchr(buf->_pp, '\n', ha_buflen(buf)); + if(t == NULL) + { + t = (buf->_rp); + buf->_rp++; + } + + *t = 0; + buf->_pp = t + 1; + + if(trim) + { + while(t > line && isspace(*(--t))) + *t = 0; + } + + /* We don't return empty strings */ + if(line[0] == 0) + return NULL; + + return line; +} + +void ha_bufnext(ha_buffer_t* buf) +{ + buffer_bump(buf, 1); + + if(!ha_buferr(buf)) + { + buf->_rp++; + buf->_pp = buf->_rp; + *(buf->_rp) = 0; + } +} + +void ha_bufcat(ha_buffer_t* buf, ...) +{ + const char* str; + va_list ap; + + va_start(ap, buf); + + while((str = va_arg(ap, char*)) != NULL) + { + int len = strlen(str); + + buffer_bump(buf, len); + + if(ha_buferr(buf)) + return; + + /* _rpoint points to teh null */ + strcpy(buf->_rp, str); + buf->_rp += len; + } +} + +void* ha_bufmalloc(ha_buffer_t* buf, size_t sz) +{ + void* ret; + + ha_bufnext(buf); + buffer_bump(buf, sz); + buf->_rp += sz; + + if(ha_buferr(buf)) + return NULL; + + ret = (void*)ha_bufdata(buf); + ha_bufnext(buf); + + return ret; +} + +/* + * Portions Copyright (c) 1995 by International Business Machines, Inc. + * + * International Business Machines, Inc. (hereinafter called IBM) grants + * permission under its copyrights to use, copy, modify, and distribute this + * Software with or without fee, provided that the above copyright notice and + * all paragraphs of this notice appear in all copies, and that the name of IBM + * not be used in connection with the marketing of any product incorporating + * the Software or modifications thereof, without specific, written prior + * permission. + * + * To the extent it has a right to do so, IBM grants an immunity from suit + * under its patents, if any, for the use, sale or manufacture of products to + * the extent that such products are used for performing Domain Name System + * dynamic updates in TCP/IP networks by means of the Software. No immunity is + * granted for any product per se or for any other function of any product. + * + * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, + * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING + * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN + * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES. + */ + +static const char BASE64C[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; +static const char PAD64C = '='; + +void ha_bufenc64(ha_buffer_t* buf, const char* src, int len) +{ + unsigned char input[3]; + unsigned char output[4]; + size_t i; + + if(len == -1) + len = strlen(src); + + while(2 < len) + { + input[0] = *src++; + input[1] = *src++; + input[2] = *src++; + len -= 3; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + output[3] = input[2] & 0x3f; + + buffer_bump(buf, 5); + + if(ha_buferr(buf)) + return; + + *(buf->_rp++) = BASE64C[output[0]]; + *(buf->_rp++) = BASE64C[output[1]]; + *(buf->_rp++) = BASE64C[output[2]]; + *(buf->_rp++) = BASE64C[output[3]]; + } + + /* Now we worry about padding. */ + if(0 != len) + { + /* Get what's left. */ + input[0] = input[1] = input[2] = '\0'; + for(i = 0; i < len; i++) + input[i] = *src++; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + + buffer_bump(buf, 5); + + if(ha_buferr(buf)) + return; + + *(buf->_rp++) = BASE64C[output[0]]; + *(buf->_rp++) = BASE64C[output[1]]; + if(len == 1) + *(buf->_rp++) = PAD64C; + else + *(buf->_rp++) = BASE64C[output[2]]; + *(buf->_rp++) = PAD64C; + } + + *(buf->_rp++) = '\0'; +} + +void ha_bufdec64(ha_buffer_t* buf, const char* src) +{ + int state; + int ch; + char* pos; + + state = 0; + + while((ch = *src++) != '\0') + { + if(isspace(ch)) /* Skip whitespace anywhere. */ + continue; + + if(ch == PAD64C) + break; + + pos = strchr(BASE64C, ch); + if(pos == 0) /* A non-base64 character. */ + break; + + buffer_bump(buf, 3); + + if(ha_buferr(buf)) + return; + + switch(state) + { + case 0: + *(buf->_rp++) = (pos - BASE64C) << 2; + state = 1; + break; + + case 1: + *(buf->_rp++) |= (pos - BASE64C) >> 4; + *(buf->_rp) = ((pos - BASE64C) & 0x0f) << 4; + state = 2; + break; + + case 2: + *(buf->_rp++) |= (pos - BASE64C) >> 2; + *(buf->_rp) = ((pos - BASE64C) & 0x03) << 6; + state = 3; + break; + + case 3: + *(buf->_rp++) |= (pos - BASE64C); + state = 0; + break; + }; + + /* TODO: Validate ending and return error if invalid somehow */ + } + + *(buf->_rp++) = '\0'; +} diff --git a/common/compat.c b/common/compat.c new file mode 100644 index 0000000..6a4b914 --- /dev/null +++ b/common/compat.c @@ -0,0 +1,30 @@ + +#include "usuals.h" +#include "compat.h" + +#ifndef HAVE_REALLOCF + +void* reallocf(void* ptr, size_t size) +{ + void* ret = realloc(ptr, size); + + if(!ret && size) + free(ptr); + + return ret; +} + +#endif + +#ifndef HAVE_STRLWR +char* strlwr(char* s) +{ + char* t = s; + while(*t) + { + *t = tolower(*t); + t++; + } + return s; +} +#endif diff --git a/common/compat.h b/common/compat.h new file mode 100644 index 0000000..c250db1 --- /dev/null +++ b/common/compat.h @@ -0,0 +1,40 @@ + + +#ifndef _COMPAT_H_ +#define _COMPAT_H_ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include + +#ifndef HAVE_STDARG_H +#error ERROR: Must have a working stdarg.h header +#else +#include +#endif + +#ifndef HAVE_REALLOCF +void* reallocf(void* p, size_t sz); +#endif + +#include + +/* TODO: Move this logic to configure */ +#if HAVE_ERR_MUTEX == 1 +# define HA_MUTEX_TYPE PTHREAD_MUTEX_ERRORCHECK_NP +#else +# if HAVE_ERR_MUTEX == 2 +# define HA_MUTEX_TYPE PTHREAD_MUTEX_ERRORCHECK +# else +# error "Need error checking mutex functionality" +# endif +#endif + +#ifndef HAVE_STRLWR +char* strlwr(char* s); +#endif + + +#endif /* _COMPAT_H_ */ diff --git a/common/hash.c b/common/hash.c new file mode 100644 index 0000000..7d67e53 --- /dev/null +++ b/common/hash.c @@ -0,0 +1,462 @@ +/* + * Originally from apache 2.0 + * Modifications for general use by + */ + +/* Copyright 2000-2004 The Apache Software Foundation + * + * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include "hash.h" + +#ifdef HASH_TIMESTAMP +#include +#endif + +#ifdef HASH_COPYKEYS + #define KEY_DATA(he) (void*)(((unsigned char*)(he)) + sizeof(*(he))) +#else + #define KEY_DATA(he) ((he)->key) +#endif + +/* + * The internal form of a hash table. + * + * The table is an array indexed by the hash of the key; collisions + * are resolved by hanging a linked list of hash entries off each + * element of the array. Although this is a really simple design it + * isn't too bad given that pools have a low allocation overhead. + */ + +typedef struct hash_entry_t hash_entry_t; + +struct hash_entry_t +{ + hash_entry_t* next; + unsigned int hash; +#ifndef HASH_COPYKEYS + const void* key; + size_t klen; +#endif + const void* val; +#ifdef HASH_TIMESTAMP + time_t stamp; +#endif +}; + +/* + * Data structure for iterating through a hash table. + * + * We keep a pointer to the next hash entry here to allow the current + * hash entry to be freed or otherwise mangled between calls to + * hash_next(). + */ +struct hash_index_t +{ + hash_t* ht; + hash_entry_t* ths; + hash_entry_t* next; + unsigned int index; +}; + +/* + * The size of the array is always a power of two. We use the maximum + * index rather than the size so that we can use bitwise-AND for + * modular arithmetic. + * The count of hash entries may be greater depending on the chosen + * collision rate. + */ +struct hash_t +{ + hash_entry_t** array; + hash_index_t iterator; /* For hash_first(...) */ + unsigned int count; + unsigned int max; +#ifdef HASH_COPYKEYS + unsigned int klen; +#endif +}; + +#define INITIAL_MAX 15 /* tunable == 2^n - 1 */ + + +/* + * Hash creation functions. + */ + +static hash_entry_t** alloc_array(hash_t* ht, unsigned int max) +{ + return malloc(sizeof(*(ht->array)) * (max + 1)); +} + +#ifdef HASH_COPYKEYS +hash_t* hash_create(size_t klen) +#else +hash_t* hash_create() +#endif +{ + hash_t* ht = malloc(sizeof(hash_t)); + if(ht) + { + ht->count = 0; + ht->max = INITIAL_MAX; + ht->array = alloc_array(ht, ht->max); +#ifdef HASH_COPYKEYS + ht->klen = klen; +#endif + + if(!ht->array) + { + free(ht); + return NULL; + } + } + return ht; +} + +void hash_free(hash_t* ht) +{ + hash_index_t* hi; + + for(hi = hash_first(ht); hi; hi = hash_next(hi)) + free(hi->ths); + + if(ht->array) + free(ht->array); + + free(ht); +} + +/* + * Hash iteration functions. + */ + +hash_index_t* hash_next(hash_index_t* hi) +{ + hi->ths = hi->next; + while(!hi->ths) + { + if(hi->index > hi->ht->max) + return NULL; + + hi->ths = hi->ht->array[hi->index++]; + } + hi->next = hi->ths->next; + return hi; +} + +hash_index_t* hash_first(hash_t* ht) +{ + hash_index_t* hi = &ht->iterator; + + hi->ht = ht; + hi->index = 0; + hi->ths = NULL; + hi->next = NULL; + return hash_next(hi); +} + +#ifdef HASH_COPYKEYS +void* hash_this(hash_index_t* hi, const void** key) +#else +void* hash_this(hash_index_t* hi, const void** key, size_t* klen) +#endif +{ + if(key) + *key = KEY_DATA(hi->ths); + +#ifndef HASH_COPYKEYS + if(klen) + *klen = hi->ths->klen; +#endif + + return (void*)hi->ths->val; +} + + +/* + * Expanding a hash table + */ + +static int expand_array(hash_t* ht) +{ + hash_index_t* hi; + hash_entry_t** new_array; + unsigned int new_max; + + new_max = ht->max * 2 + 1; + new_array = alloc_array(ht, new_max); + + if(!new_array) + return 0; + + for(hi = hash_first(ht); hi; hi = hash_next(hi)) + { + unsigned int i = hi->ths->hash & new_max; + hi->ths->next = new_array[i]; + new_array[i] = hi->ths; + } + + if(ht->array) + free(ht->array); + + ht->array = new_array; + ht->max = new_max; + return 1; +} + +/* + * This is where we keep the details of the hash function and control + * the maximum collision rate. + * + * If val is non-NULL it creates and initializes a new hash entry if + * there isn't already one there; it returns an updatable pointer so + * that hash entries can be removed. + */ + +#ifdef HASH_COPYKEYS +static hash_entry_t** find_entry(hash_t* ht, const void* key, const void* val) +#else +static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const void* val) +#endif +{ + hash_entry_t** hep; + hash_entry_t* he; + const unsigned char* p; + unsigned int hash; + size_t i; + +#ifdef HASH_COPYKEYS + size_t klen = ht->klen; +#endif + + /* + * This is the popular `times 33' hash algorithm which is used by + * perl and also appears in Berkeley DB. This is one of the best + * known hash functions for strings because it is both computed + * very fast and distributes very well. + * + * The originator may be Dan Bernstein but the code in Berkeley DB + * cites Chris Torek as the source. The best citation I have found + * is "Chris Torek, Hash function for text in C, Usenet message + * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich + * Salz's USENIX 1992 paper about INN which can be found at + * . + * + * The magic of number 33, i.e. why it works better than many other + * constants, prime or not, has never been adequately explained by + * anyone. So I try an explanation: if one experimentally tests all + * multipliers between 1 and 256 (as I did while writing a low-level + * data structure library some time ago) one detects that even + * numbers are not useable at all. The remaining 128 odd numbers + * (except for the number 1) work more or less all equally well. + * They all distribute in an acceptable way and this way fill a hash + * table with an average percent of approx. 86%. + * + * If one compares the chi^2 values of the variants (see + * Bob Jenkins ``Hashing Frequently Asked Questions'' at + * http://burtleburtle.net/bob/hash/hashfaq.html for a description + * of chi^2), the number 33 not even has the best value. But the + * number 33 and a few other equally good numbers like 17, 31, 63, + * 127 and 129 have nevertheless a great advantage to the remaining + * numbers in the large set of possible multipliers: their multiply + * operation can be replaced by a faster operation based on just one + * shift plus either a single addition or subtraction operation. And + * because a hash function has to both distribute good _and_ has to + * be very fast to compute, those few numbers should be preferred. + * + * -- Ralf S. Engelschall + */ + hash = 0; + +#ifndef HASH_COPYKEYS + if(klen == HASH_KEY_STRING) + { + for(p = key; *p; p++) + hash = hash * 33 + *p; + + klen = p - (const unsigned char *)key; + } + else +#endif + { + for(p = key, i = klen; i; i--, p++) + hash = hash * 33 + *p; + } + + /* scan linked list */ + for(hep = &ht->array[hash & ht->max], he = *hep; + he; hep = &he->next, he = *hep) + { + if(he->hash == hash && +#ifndef HASH_COPYKEYS + he->klen == klen && +#endif + memcmp(KEY_DATA(he), key, klen) == 0) + break; + } + + if(he || !val) + return hep; + + /* add a new entry for non-NULL val */ +#ifdef HASH_COPYKEYS + he = malloc(sizeof(*he) + klen); +#else + he = malloc(sizeof(*he)); +#endif + + if(he) + { +#ifdef HASH_COPYKEYS + /* Key data points past end of entry */ + memcpy(KEY_DATA(he), key, klen); +#else + /* Key points to external data */ + he->key = key; + he->klen = klen; +#endif + + he->next = NULL; + he->hash = hash; + he->val = val; + +#ifdef HASH_TIMESTAMP + he->stamp = 0; +#endif + + *hep = he; + ht->count++; + } + + return hep; +} + +#ifdef HASH_COPYKEYS +void* hash_get(hash_t* ht, const void *key) +{ + hash_entry_t** he = find_entry(ht, key, NULL); +#else +void* hash_get(hash_t* ht, const void *key, size_t klen) +{ + hash_entry_t** he = find_entry(ht, key, klen, NULL); +#endif + + if(he && *he) + return (void*)((*he)->val); + else + return NULL; +} + +#ifdef HASH_COPYKEYS +int hash_set(hash_t* ht, const void* key, const void* val) +{ + hash_entry_t** hep = find_entry(ht, key, val); +#else +int hash_set(hash_t* ht, const void* key, size_t klen, const void* val) +{ + hash_entry_t** hep = find_entry(ht, key, klen, val); +#endif + + if(hep && *hep) + { + if(val) + { + /* replace entry */ + (*hep)->val = val; + +#ifdef HASH_TIMESTAMP + /* Update or set the timestamp */ + (*hep)->stamp = time(NULL); +#endif + + /* check that the collision rate isn't too high */ + if(ht->count > ht->max) + { + if(!expand_array(ht)) + return 0; + } + + return 1; + } + } + + return 0; +} + +#ifdef HASH_COPYKEYS +void hash_rem(hash_t* ht, const void* key) +{ + hash_entry_t** hep = find_entry(ht, key, NULL); +#else +void hash_rem(hash_t* ht, const void* key, size_t klen) +{ + hash_entry_t** hep = find_entry(ht, key, klen, NULL); +#endif + + if(hep && *hep) + { + hash_entry_t* old = *hep; + *hep = (*hep)->next; + --ht->count; + free(old); + } +} + +unsigned int hash_count(hash_t* ht) +{ + return ht->count; +} + +#ifdef HASH_TIMESTAMP +int hash_purge(hash_t* ht, time_t stamp) +{ + hash_index_t* hi; + int r = 0; + + for(hi = hash_first(ht); hi; hi = hash_next(hi)) + { + if(hi->ths->stamp < stamp) + { + /* No need to check for errors as we're deleting */ +#ifdef HASH_COPYKEYS + hash_rem(ht, KEY_DATA(hi->ths)); +#else + hash_rem(ht, hi->ths->key, hi->ths->klen); +#endif + + r++; + } + } + + return r; +} + +#ifdef HASH_COPYKEYS +void* hash_touch(hash_index_t* hi, const void** key); +{ + hash_entry_t** hep = find_entry(ht, key, NULL); +#else +void* hash_touch(hash_index_t* hi, const void** key, size_t* klen); +{ + hash_entry_t** hep = find_entry(ht, key, klen, NULL); +#endif + + if(he && *he) + ((*he)->stamp) = time(NULL); +} + +#endif /* HASH_TIMESTAMP */ diff --git a/common/hash.h b/common/hash.h new file mode 100644 index 0000000..9e8174c --- /dev/null +++ b/common/hash.h @@ -0,0 +1,171 @@ +/* + * Originally from apache 2.0 + * Modifications for general use by + */ + +/* Copyright 2000-2004 The Apache Software Foundation + * + * Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __HASH_H__ +#define __HASH_H__ + +/* + * Options to define. You need to build both this file and + * the corresponding hash.c file with whatever options you set here + */ + +/* Keep timestamps for the entries */ +#define HASH_TIMESTAMP 1 + +/* Keep key values internally */ +#define HASH_COPYKEYS 1 + + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * When passing a key to hash_set or hash_get, this value can be passed to + * indicate a string-valued key, and have hash compute the length automatically. + */ +#define HASH_KEY_STRING (-1) + +/* Abstract type for hash tables. */ +typedef struct hash_t hash_t; + +/* Abstract type for scanning hash tables. */ +typedef struct hash_index_t hash_index_t; + +/* Create a hash table */ +#ifdef HASH_COPYKEYS + hash_t* hash_create(size_t klen); +#else + hash_t* hash_create(); +#endif + +/* To release all resources for a hash table */ +void hash_free(hash_t* ht); + +/** + * Associate a value with a key in a hash table. + * + * ht The hash table + * key Pointer to the key + * klen Length of the key. Can be HASH_KEY_STRING to use the string length. + * val Value to associate with the key + * + * val must not be null + */ +#ifdef HASH_COPYKEYS + int hash_set(hash_t* ht, const void* key, const void* val); +#else + int hash_set(hash_t* ht, const void* key, size_t klen, const void* val); +#endif + +/** + * Remove a value and key form the hash table + * + * ht The hash table + * key Pointer to the key + * klen Length of the key. Can be HASH_KEY_STRING to use the string length + */ +#ifdef HASH_COPYKEYS + void hash_rem(hash_t* ht, const void* key); +#else + void hash_rem(hash_t* ht, const void* key, size_t klen); +#endif + +/** + * Look up the value associated with a key in a hash table. + * + * ht The hash table + * key Pointer to the key + * klen Length of the key. Can be APR_HASH_KEY_STRING to use the string length. + * + * Returns NULL if the key is not present. + */ +#ifdef HASH_COPYKEYS + void* hash_get(hash_t* ht, const void* key); +#else + void* hash_get(hash_t* ht, const void* key, size_t klen); +#endif + +/** + * Start iterating over the entries in a hash table. + * + * ht The hash table + * + * There is no restriction on adding or deleting hash entries during + * an iteration (although the results may be unpredictable unless all you do + * is delete the current entry). Only one iteration can be in progress at once. + */ +hash_index_t* hash_first(hash_t* ht); + +/** + * Continue iterating over the entries in a hash table. + * + * hi The iteration state + * + * Returns a pointer to the updated iteration state. + * NULL if there are no more entries. + */ +hash_index_t* hash_next(hash_index_t* hi); + +/** + * Get the current entry's details from the iteration state. + * + * hi The iteration state + * key Return pointer for the pointer to the key. + * klen Return pointer for the key length. + * val Return pointer for the associated value. + * + * The return pointers should point to a variable that will be set to the + * corresponding data, or they may be NULL if the data isn't interesting. + */ +#ifdef HASH_COPYKEYS + void* hash_this(hash_index_t* hi, const void** key); +#else + void* hash_this(hash_index_t* hi, const void** key, size_t* klen); +#endif + +/** + * Purge entries before a certain timestamp + */ +#ifdef HASH_TIMESTAMP +int hash_purge(hash_t* ht, time_t stamp); + +#ifdef HASH_COPYKEYS + void hash_touch(hash_index_t* hi, const void** key); +#else + void hash_touch(hash_index_t* hi, const void** key, size_t* klen); +#endif +#endif + +/** + * Get the number of key/value pairs in the hash table. + * + * ht The hash table + * + * The number of key/value pairs in the hash table. + */ +unsigned int hash_count(hash_t* ht); + + +#ifdef __cplusplus +} +#endif + +#endif /* __HASH_H__ */ diff --git a/common/md5.c b/common/md5.c new file mode 100644 index 0000000..c909bb3 --- /dev/null +++ b/common/md5.c @@ -0,0 +1,228 @@ +/* + * This code implements the MD5 message-digest algorithm. + * The algorithm is due to Ron Rivest. This code was + * written by Colin Plumb in 1993, no copyright is claimed. + * This code is in the public domain; do with it what you wish. + * + * Equivalent code is available from RSA Data Security, Inc. + * This code has been tested against that, and is equivalent, + * except that you don't need to include two pages of legalese + * with every copy. + * + * To compute the message digest of a chunk of bytes, declare an + * MD5Context structure, pass it to MD5Init, call MD5Update as + * needed on buffers full of bytes, and then call MD5Final, which + * will fill a supplied 16-byte array with the digest. + */ + +#include +#include "md5.h" + +#ifdef BIG_ENDIAN +void +byteSwap(unsigned int *buf, unsigned words) +{ + unsigned char *p = (unsigned char *)buf; + + do { + *buf++ = (unsigned int)((unsigned)p[3] << 8 | p[2]) << 16 | + ((unsigned)p[1] << 8 | p[0]); + p += 4; + } while (--words); +} +#else +#define byteSwap(buf,words) +#endif + +/* + * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious + * initialization constants. + */ +void +MD5Init(struct MD5Context *ctx) +{ + ctx->buf[0] = 0x67452301; + ctx->buf[1] = 0xefcdab89; + ctx->buf[2] = 0x98badcfe; + ctx->buf[3] = 0x10325476; + + ctx->bytes[0] = 0; + ctx->bytes[1] = 0; +} + +/* + * Update context to reflect the concatenation of another buffer full + * of bytes. + */ +void +MD5Update(struct MD5Context *ctx, const unsigned char* buf, unsigned len) +{ + unsigned int t; + + /* Update byte count */ + + t = ctx->bytes[0]; + if ((ctx->bytes[0] = t + len) < t) + ctx->bytes[1]++; /* Carry from low to high */ + + t = 64 - (t & 0x3f); /* Space available in ctx->in (at least 1) */ + if (t > len) { + memcpy((unsigned char *)ctx->in + 64 - t, buf, len); + return; + } + /* First chunk is an odd size */ + memcpy((unsigned char *)ctx->in + 64 - t, buf, t); + byteSwap(ctx->in, 16); + MD5Transform(ctx->buf, ctx->in); + buf += t; + len -= t; + + /* Process data in 64-byte chunks */ + while (len >= 64) { + memcpy(ctx->in, buf, 64); + byteSwap(ctx->in, 16); + MD5Transform(ctx->buf, ctx->in); + buf += 64; + len -= 64; + } + + /* Handle any remaining bytes of data. */ + memcpy(ctx->in, buf, len); +} + +/* + * Final wrapup - pad to 64-byte boundary with the bit pattern + * 1 0* (64-bit count of bits processed, MSB-first) + */ +void +MD5Final(unsigned char digest[16], struct MD5Context *ctx) +{ + int count = ctx->bytes[0] & 0x3f; /* Number of bytes in ctx->in */ + unsigned char *p = (unsigned char *)ctx->in + count; + + /* Set the first char of padding to 0x80. There is always room. */ + *p++ = 0x80; + + /* Bytes of padding needed to make 56 bytes (-8..55) */ + count = 56 - 1 - count; + + if (count < 0) { /* Padding forces an extra block */ + memset(p, 0, (unsigned int)count + 8); + byteSwap(ctx->in, 16); + MD5Transform(ctx->buf, ctx->in); + p = (unsigned char *)ctx->in; + count = 56; + } + memset(p, 0, (unsigned int)count); + byteSwap(ctx->in, 14); + + /* Append length in bits and transform */ + ctx->in[14] = ctx->bytes[0] << 3; + ctx->in[15] = ctx->bytes[1] << 3 | ctx->bytes[0] >> 29; + MD5Transform(ctx->buf, ctx->in); + + byteSwap(ctx->buf, 4); + memcpy(digest, ctx->buf, 16); + memset(ctx, 0, sizeof(ctx)); /* In case it's sensitive */ +} + +/* The four core functions - F1 is optimized somewhat */ + +/* #define F1(x, y, z) (x & y | ~x & z) */ +#define F1(x, y, z) (z ^ (x & (y ^ z))) +#define F2(x, y, z) F1(z, x, y) +#define F3(x, y, z) (x ^ y ^ z) +#define F4(x, y, z) (y ^ (x | ~z)) + +/* This is the central step in the MD5 algorithm. */ +#define MD5STEP(f,w,x,y,z,in,s) \ + (w += f(x,y,z) + in, w = (w<>(32-s)) + x) + +/* + * The core of the MD5 algorithm, this alters an existing MD5 hash to + * reflect the addition of 16 longwords of new data. MD5Update blocks + * the data and converts bytes into longwords for this routine. + */ +void +MD5Transform(unsigned int buf[4], unsigned int const in[16]) +{ + register unsigned int a, b, c, d; + + a = buf[0]; + b = buf[1]; + c = buf[2]; + d = buf[3]; + + MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7); + MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12); + MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17); + MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22); + MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7); + MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12); + MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17); + MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22); + MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7); + MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12); + MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17); + MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22); + MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7); + MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12); + MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17); + MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22); + + MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5); + MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9); + MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14); + MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20); + MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5); + MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9); + MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14); + MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20); + MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5); + MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9); + MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14); + MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20); + MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5); + MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9); + MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14); + MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20); + + MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4); + MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11); + MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16); + MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23); + MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4); + MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11); + MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16); + MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23); + MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4); + MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11); + MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16); + MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23); + MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4); + MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11); + MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16); + MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23); + + MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6); + MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10); + MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15); + MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21); + MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6); + MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10); + MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15); + MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21); + MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6); + MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10); + MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15); + MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21); + MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6); + MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10); + MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15); + MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21); + + buf[0] += a; + buf[1] += b; + buf[2] += c; + buf[3] += d; +} diff --git a/common/md5.h b/common/md5.h new file mode 100644 index 0000000..62cbf2b --- /dev/null +++ b/common/md5.h @@ -0,0 +1,49 @@ +/* + * This is the header file for the MD5 message-digest algorithm. + * The algorithm is due to Ron Rivest. This code was + * written by Colin Plumb in 1993, no copyright is claimed. + * This code is in the public domain; do with it what you wish. + * + * Equivalent code is available from RSA Data Security, Inc. + * This code has been tested against that, and is equivalent, + * except that you don't need to include two pages of legalese + * with every copy. + * + * To compute the message digest of a chunk of bytes, declare an + * MD5Context structure, pass it to MD5Init, call MD5Update as + * needed on buffers full of bytes, and then call MD5Final, which + * will fill a supplied 16-byte array with the digest. + * + * Changed so as no longer to depend on Colin Plumb's `usual.h' + * header definitions; now uses stuff from dpkg's config.h + * - Ian Jackson . + * Still in the public domain. + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef MD5_H +#define MD5_H + +#define md5byte unsigned char + +struct MD5Context { + unsigned int buf[4]; + unsigned int bytes[2]; + unsigned int in[16]; +}; + +typedef struct MD5Context MD5_CTX; + +void MD5Init(struct MD5Context *context); +void MD5Update(struct MD5Context *context, const md5byte* buf, unsigned len); +void MD5Final(unsigned char digest[16], struct MD5Context *context); +void MD5Transform(unsigned int buf[4], unsigned int const in[16]); + +#ifdef __cplusplus +} +#endif + +#endif /* !MD5_H */ -- cgit v1.2.3