From e5fbc3c2bb1c06106e5fea0e032868219cea9d50 Mon Sep 17 00:00:00 2001 From: mquinson Date: Wed, 14 May 2008 21:21:10 +0000 Subject: [PATCH 1/1] An implementation of the SHA1 hashing algorithm git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@5427 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- include/Makefile.am | 2 +- include/xbt/hash.h | 30 +++++++ src/Makefile.am | 12 +-- src/xbt/xbt_sha.c | 201 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 239 insertions(+), 6 deletions(-) create mode 100644 include/xbt/hash.h create mode 100644 src/xbt/xbt_sha.c diff --git a/include/Makefile.am b/include/Makefile.am index 8df5f674b6..9b3d845c3e 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -10,7 +10,7 @@ nobase_include_HEADERS = \ xbt/misc.h \ xbt/sysdep.h \ xbt/virtu.h \ - xbt/str.h xbt/strbuff.h \ + xbt/str.h xbt/strbuff.h xbt/hash.h \ xbt/function_types.h \ xbt/asserts.h xbt/ex.h \ xbt/log.h \ diff --git a/include/xbt/hash.h b/include/xbt/hash.h new file mode 100644 index 0000000000..43b483ca59 --- /dev/null +++ b/include/xbt/hash.h @@ -0,0 +1,30 @@ +/* $Id: str.h,v 1.5 2007/05/02 10:08:55 mquinson Exp $ */ + +/* hash.h - Various hashing functions. */ + +/* Copyright (c) 2007, Martin Quinson. */ +/* All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef XBT_HASH_H +#define XBT_HASH_H +#include "xbt/str.h" + +/* Chord needs a SHA1 algorithm. Let's drop it in there */ +typedef struct s_xbt_sha_ s_xbt_sha_t, *xbt_sha_t; + +XBT_PUBLIC(xbt_sha_t) xbt_sha_new (void); +XBT_PUBLIC(void) xbt_sha_free (xbt_sha_t sha); + +XBT_PUBLIC(void) xbt_sha_feed (xbt_sha_t sha, const unsigned char *data, size_t len); +XBT_PUBLIC(void) xbt_sha_reset (xbt_sha_t sha); + +XBT_PUBLIC(void) xbt_sha_print (xbt_sha_t sha, char *hash); +XBT_PUBLIC(char *) xbt_sha_read(xbt_sha_t sha); + +XBT_PUBLIC(void) xbt_sha (const char *data, char *hash); + + +#endif /* XBT_HASH_H */ diff --git a/src/Makefile.am b/src/Makefile.am index 28bcb0b0df..4f4a33692b 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -126,7 +126,7 @@ VERSION_INFO= -version-info 2:0:0 XBT_SRC=\ \ - xbt/snprintf.c xbt/xbt_str.c xbt/xbt_strbuff.c \ + xbt/snprintf.c xbt/xbt_str.c xbt/xbt_strbuff.c xbt/xbt_sha.c \ xbt/ex.c \ \ xbt_modinter.h gras_modinter.h \ @@ -381,11 +381,11 @@ else noinst_PROGRAMS=testall TEST_CFILES=xbt/cunit.c xbt/ex.c \ xbt/dynar.c xbt/dict.c xbt/set.c xbt/swag.c \ - xbt/xbt_str.c \ + xbt/xbt_str.c xbt/xbt_sha.c \ xbt/config.c -TEST_UNITS= @builddir@/cunit_unit.c @builddir@/ex_unit.c \ - @builddir@/dynar_unit.c @builddir@/dict_unit.c @builddir@/set_unit.c @builddir@/swag_unit.c \ - @builddir@/xbt_str_unit.c \ +TEST_UNITS= @builddir@/cunit_unit.c @builddir@/ex_unit.c \ + @builddir@/dynar_unit.c @builddir@/dict_unit.c @builddir@/set_unit.c @builddir@/swag_unit.c \ + @builddir@/xbt_str_unit.c @builddir@/xbt_sha_unit.c\ @builddir@/config_unit.c BUILT_SOURCES=../include/surf/simgrid_dtd.h surf/simgrid_dtd.c \ @@ -409,6 +409,8 @@ CLEANFILES=$(TEST_UNITS) @top_srcdir@/tools/sg_unit_extractor.pl $^ @builddir@/xbt_str_unit.c: xbt/xbt_str.c @top_srcdir@/tools/sg_unit_extractor.pl $^ +@builddir@/xbt_sha_unit.c: xbt/xbt_sha.c + @top_srcdir@/tools/sg_unit_extractor.pl $^ @builddir@/dynar_unit.c: xbt/dynar.c @top_srcdir@/tools/sg_unit_extractor.pl $^ @builddir@/dict_unit.c: xbt/dict.c diff --git a/src/xbt/xbt_sha.c b/src/xbt/xbt_sha.c new file mode 100644 index 0000000000..20baf37467 --- /dev/null +++ b/src/xbt/xbt_sha.c @@ -0,0 +1,201 @@ +/* $Id$ */ +/* xbt_sha.c - SHA1 hash function */ + +/* Initial version part of iksemel (XML parser for Jabber) + * Copyright (C) 2000-2003 Gurer Ozen + * This code is free software; you can redistribute it and/or + * modify it under the terms of GNU Lesser General Public License. */ +/* Adapted to fit into SimGrid by Martin Quinson. */ + +#include "xbt/sysdep.h" +#include "xbt/hash.h" + +struct s_xbt_sha_ { + unsigned int hash[5]; + unsigned int buf[80]; + int blen; + unsigned int lenhi, lenlo; +}; +static void sha_calculate (xbt_sha_t sha); + +/* ************** */ +/* User Interface */ +/* ************** */ + +/** @brief constructor */ +xbt_sha_t xbt_sha_new (void) { + xbt_sha_t sha; + + sha = xbt_new(s_xbt_sha_t,1); + xbt_sha_reset (sha); + + return sha; +} + +/** @brief destructor */ +void xbt_sha_free (xbt_sha_t sha) { + free (sha); +} + +void xbt_sha_reset (xbt_sha_t sha) { + memset (sha, 0, sizeof (s_xbt_sha_t)); + sha->hash[0] = 0x67452301; + sha->hash[1] = 0xefcdab89; + sha->hash[2] = 0x98badcfe; + sha->hash[3] = 0x10325476; + sha->hash[4] = 0xc3d2e1f0; +} + +/* @brief Add some more data to the buffer */ +void xbt_sha_feed (xbt_sha_t sha, const unsigned char *data, size_t len) { + int i; + + for (i=0; ibuf[sha->blen / 4] <<= 8; + sha->buf[sha->blen / 4] |= (unsigned int)data[i]; + if ((++sha->blen) % 64 == 0) { + sha_calculate (sha); + sha->blen = 0; + } + sha->lenlo += 8; + sha->lenhi += (sha->lenlo < 8); + } +} + +/* finalize computation before displaying the result */ +static void xbt_sha_finalize (xbt_sha_t sha) { + unsigned char pad[8]; + unsigned char padc; + + pad[0] = (unsigned char)((sha->lenhi >> 24) & 0xff); + pad[1] = (unsigned char)((sha->lenhi >> 16) & 0xff); + pad[2] = (unsigned char)((sha->lenhi >> 8) & 0xff); + pad[3] = (unsigned char)(sha->lenhi & 0xff); + pad[4] = (unsigned char)((sha->lenlo >> 24) & 0xff); + pad[5] = (unsigned char)((sha->lenlo >> 16) & 0xff); + pad[6] = (unsigned char)((sha->lenlo >> 8) & 0xff); + pad[7] = (unsigned char)(sha->lenlo & 255); + + padc = 0x80; + xbt_sha_feed (sha, &padc, 1); + + padc = 0x00; + while (sha->blen != 56) + xbt_sha_feed (sha, &padc, 1); + + xbt_sha_feed (sha, pad, 8); +} + +/** @brief returns the sha hash into a newly allocated buffer (+ reset sha object) */ +char *xbt_sha_read(xbt_sha_t sha) { + char *res = xbt_malloc(40); + xbt_sha_print(sha,res); + return res; +} + +/** @brief copy the content sha hash into the @a hash pre-allocated string (and reset buffer) */ +void xbt_sha_print (xbt_sha_t sha, char *hash) { + int i; + + xbt_sha_finalize(sha); + for (i=0; i<5; i++) { + sprintf (hash, "%08x", sha->hash[i]); + hash += 8; + } +} + + +/** @brief simply compute a SHA1 hash and copy it to the provided buffer */ +void xbt_sha (const char *data, char *hash) { + s_xbt_sha_t sha; + + xbt_sha_reset (&sha); + xbt_sha_feed (&sha, (const unsigned char*)data, strlen (data)); + + xbt_sha_print (&sha, hash); +} + +/* ********************* */ +/* Core of the algorithm */ +/* ********************* */ + +#define SRL(x,y) (((x) << (y)) | ((x) >> (32-(y)))) +#define SHA(a,b,f,c) \ + for (i= (a) ; i<= (b) ; i++) { \ + TMP = SRL(A,5) + ( (f) ) + E + sha->buf[i] + (c) ; \ + E = D; \ + D = C; \ + C = SRL(B,30); \ + B = A; \ + A = TMP; \ + } + +static void sha_calculate (xbt_sha_t sha) +{ + int i; + unsigned int A, B, C, D, E, TMP; + + for (i=16; i<80; i++) + sha->buf[i] = SRL (sha->buf[i-3] ^ sha->buf[i-8] ^ sha->buf[i-14] ^ sha->buf[i-16], 1); + + A = sha->hash[0]; + B = sha->hash[1]; + C = sha->hash[2]; + D = sha->hash[3]; + E = sha->hash[4]; + + SHA (0, 19, ((C^D)&B)^D, 0x5a827999); + SHA (20, 39, B^C^D, 0x6ed9eba1); + SHA (40, 59, (B&C)|(D&(B|C)), 0x8f1bbcdc); + SHA (60, 79, B^C^D, 0xca62c1d6); + + sha->hash[0] += A; + sha->hash[1] += B; + sha->hash[2] += C; + sha->hash[3] += D; + sha->hash[4] += E; +} + +/* ************* */ +/* Testing stuff */ +/* ************* */ +#ifdef SIMGRID_TEST +#include "xbt/hash.h" +#include "portable.h" /* hexa_str */ + +static char* mycmp(const char *p1, const char *p2,size_t n) { + int i; + + for (i=0; i