Merge branch 'refs/heads/t/sha3' into master
authorAndre Noll <maan@tuebingen.mpg.de>
Thu, 15 Oct 2020 14:20:54 +0000 (16:20 +0200)
committerAndre Noll <maan@tuebingen.mpg.de>
Thu, 15 Oct 2020 14:20:54 +0000 (16:20 +0200)
This code was written long ago and was sitting in a development branch
for some years. As such it was part of the pu branch and so has seen
some testing.

There's an easy conflict in fsck.c where one side added a function
parameter and the other renamed some variables.

* refs/heads/t/sha3:
  Version 3 tables.
  Add sha3 implementation, introduce version-2 tables.
  Prepare hash_function() for multiple hash algorithms.
  Store table version in struct osl_table.
  Initialize column name hash *after* table version is known.
  osl_open_table(): Remove pointless directory check.
  Remove sha1.h.
  Remove COMPAT_TABLE_VERSION.

Makefile
fsck.c
hash.h
osl.c
osl_core.h
sha1.h [deleted file]
sha256.c [new file with mode: 0644]
sha3.c [new file with mode: 0644]

index 87c7d29..fd10f43 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -15,8 +15,8 @@ includedir := $(PREFIX)/include
 bindir := $(PREFIX)/bin
 mandir := $(PREFIX)/man/man1
 
-objects := osl.o util.o rbtree.o sha1.o
-fsck_objects := fsck.o osl.o util.o rbtree.o sha1.o oslfsck.lsg.o
+objects := osl.o util.o rbtree.o sha1.o sha3.o sha256.o
+fsck_objects := fsck.o osl.o util.o rbtree.o sha1.o sha3.o sha256.o oslfsck.lsg.o
 deps := $(sort $(objects:.o=.d) $(fsck_objects:.o=.d))
 headers := osl.h
 executables := oslfsck
diff --git a/fsck.c b/fsck.c
index e814df5..53b4a9b 100644 (file)
--- a/fsck.c
+++ b/fsck.c
@@ -722,7 +722,7 @@ static int check_disk_storage_presence(struct osl_table *t)
                ret = get_mapped_object(t, dsnc, k, &obj);
                if (ret < 0)
                        return ret;
-               hash_object(&obj, hashes + k * HASH_SIZE);
+               hash_object(t, &obj, hashes + k * HASH_SIZE);
                hash_obj.data = hashes + k * HASH_SIZE;
                osl_add_row(hash_tree_table, &hash_obj);
                ds_name = disk_storage_name_of_hash(t, hashes + k * HASH_SIZE);
@@ -876,21 +876,23 @@ static void set_dummy_contents(struct osl_table_description *desc)
 static int fsck_init(struct osl_table_description *desc, struct osl_table **t)
 {
        struct osl_object map;
-       int ret = map_index(desc, &map);
+       int version, ret = map_index(desc, &map);
 
        if (ret < 0)
                goto out;
-       ret = read_table_desc(&map, desc);
+       ret = read_table_desc(&map, desc); /* checks table version */
        if (ret < 0) {
                osl_munmap(map.data, map.size);
                goto out;
        }
+       version = ret;
        set_dummy_contents(desc);
        ret = init_table_structure(desc, t);
        if (ret < 0) {
                osl_munmap(map.data, map.size);
                goto out;
        }
+       (*t)->version = version;
        DEBUG_LOG("unmapping index\n");
        osl_munmap(map.data, map.size);
        if (OPT_GIVEN(FORCE))
@@ -1043,7 +1045,7 @@ static int dump_row(struct osl_table *t, unsigned row_num, const char *row_dir)
        ret = get_mapped_object(t, dsnc, row_num, &obj);
        if (ret < 0)
                return ret;
-       hash_object(&obj, hash);
+       hash_object(t, &obj, hash);
        ds_name = disk_storage_name_of_hash(t, hash);
        FOR_EACH_DISK_STORAGE_COLUMN(i, t, cd) {
                filename = disk_storage_path(t, i, ds_name);
diff --git a/hash.h b/hash.h
index 0feee84..585ef4e 100644 (file)
--- a/hash.h
+++ b/hash.h
 /** hash arrays are always unsigned char. */
 #define HASH_TYPE unsigned char
 
-#include "sha1.h"
-/** Our own sha1 implementation, see sha1.c. */
-#define hash_function sha1_hash
+/** Size of the hash value in bytes. */
+#define HASH_SIZE 20
+
+void sha1_hash(const char *data, unsigned long len, unsigned char *result);
+void sha3_hash(const char *data, unsigned long len, unsigned char *result);
+void sha256_hash(const char *data, unsigned long len, unsigned char *result);
+
+static inline void hash_function(uint8_t table_version, const char *data,
+               unsigned long len, unsigned char *result)
+{
+       switch (table_version) {
+       case 1: return sha1_hash(data, len, result);
+       case 2: return sha3_hash(data, len, result);
+       case 3: return sha256_hash(data, len, result);
+       }
+       assert(0);
+}
 
 /**
  * Compare two hashes.
diff --git a/osl.c b/osl.c
index 17bddeb..9480325 100644 (file)
--- a/osl.c
+++ b/osl.c
@@ -168,7 +168,7 @@ static char *disk_storage_name_of_object(const struct osl_table *t,
        const struct osl_object *obj)
 {
        HASH_TYPE hash[HASH_SIZE];
-       hash_object(obj, hash);
+       hash_object(t, obj, hash);
        return disk_storage_name_of_hash(t, hash);
 }
 
@@ -186,9 +186,10 @@ static int disk_storage_name_of_row(const struct osl_table *t,
        return -E_OSL_NOMEM;
 }
 
-static void column_name_hash(const char *col_name, HASH_TYPE *hash)
+static void column_name_hash(const struct osl_table *t, const char *col_name,
+               HASH_TYPE *hash)
 {
-       hash_function(col_name, strlen(col_name), hash);
+       hash_function(t->version, col_name, strlen(col_name), hash);
 }
 
 static int init_column_descriptions(struct osl_table *t)
@@ -205,7 +206,6 @@ static int init_column_descriptions(struct osl_table *t)
        /* the size of the index header without column descriptions */
        t->index_header_size = IDX_COLUMN_DESCRIPTIONS;
        FOR_EACH_COLUMN(i, t->desc, cd) {
-               struct osl_column *col = t->columns + i;
                if (cd->storage_flags & OSL_RBTREE) {
                        if (!cd->compare_function)
                                return -E_OSL_NO_COMPARE_FUNC;
@@ -219,7 +219,6 @@ static int init_column_descriptions(struct osl_table *t)
                if (ret < 0)
                        goto err;
                t->index_header_size += index_column_description_size(cd->name);
-               column_name_hash(cd->name, col->name_hash);
                ret = -E_OSL_DUPLICATE_COL_NAME;
                for (j = i + 1; j < t->desc->num_columns; j++) {
                        const char *name2 = get_column_description(t->desc,
@@ -342,14 +341,14 @@ err:
  * Read the index header, check for the osl magic string and the table version
  * number.  Read all information stored in the index header into \a desc.
  *
- * \return Standard.
+ * \return The on-disk table version number on success, negative on errors.
  *
  * \sa struct osl_table_description, osl_create_table.
  */
 int read_table_desc(struct osl_object *map, struct osl_table_description *desc)
 {
        char *buf = map->data;
-       uint8_t version, compat_version, create_version;
+       uint8_t table_version;
        uint16_t header_size;
        int ret, i;
        unsigned offset;
@@ -359,20 +358,11 @@ int read_table_desc(struct osl_object *map, struct osl_table_description *desc)
                return -E_OSL_SHORT_TABLE;
        if (strncmp(buf + IDX_OSL_MAGIC, OSL_MAGIC, strlen(OSL_MAGIC)))
                return -E_OSL_NO_MAGIC;
-       version = read_u8(buf + IDX_VERSION);
-       /*
-        * The on-disk version consists of two version numbers: the
-        * create_version (low 4 bits) is the CURRENT_TABLE_VERSION version
-        * number of the library that created the table, and compat_version
-        * (high 4 bits) tells us the lowest version of the library that can
-        * still read this table.
-        */
-       create_version = version & 0xf;
-       compat_version = version >> 4;
-       INFO_LOG("create_version: %u, compat_version: %u\n", create_version,
-               compat_version);
-       if (create_version < MIN_TABLE_VERSION /* table too old */
-               || compat_version > CURRENT_TABLE_VERSION) /* libosl too old */
+       table_version = read_u8(buf + IDX_VERSION);
+       INFO_LOG("osl versions (table/min/current): %u/%u/%u\n",
+               table_version, MIN_TABLE_VERSION, CURRENT_TABLE_VERSION);
+       if (table_version < MIN_TABLE_VERSION /* table too old */
+               || table_version > CURRENT_TABLE_VERSION) /* libosl too old */
                return -E_OSL_VERSION_MISMATCH;
        desc->flags = read_u8(buf + IDX_TABLE_FLAGS);
        desc->num_columns = read_u16(buf + IDX_NUM_COLUMNS);
@@ -417,7 +407,7 @@ int read_table_desc(struct osl_object *map, struct osl_table_description *desc)
                        offset, header_size);
                goto err;
        }
-       return 1;
+       return table_version;
 err:
        FOR_EACH_COLUMN(i, desc, cd)
                free(cd->name);
@@ -438,6 +428,7 @@ static int compare_table_descriptions(struct osl_table *t)
        ret = read_table_desc(&t->index_map, &desc);
        if (ret < 0)
                return ret;
+       t->version = ret;
        ret = -E_OSL_BAD_TABLE_FLAGS;
        if (desc.flags != t->desc->flags)
                goto out;
@@ -507,8 +498,7 @@ static int create_table_index(struct osl_table *t)
        sprintf(buf + IDX_OSL_MAGIC, "%s", OSL_MAGIC);
        write_u8(buf + IDX_TABLE_FLAGS, t->desc->flags);
        write_u8(buf + IDX_DIRTY_FLAG, 0);
-       write_u8(buf + IDX_VERSION, CURRENT_TABLE_VERSION
-               + (COMPAT_TABLE_VERSION << 4));
+       write_u8(buf + IDX_VERSION, t->version);
        write_u16(buf + IDX_NUM_COLUMNS, t->num_mapped_columns + t->num_disk_storage_columns);
        write_u16(buf + IDX_HEADER_SIZE, t->index_header_size);
        offset = IDX_COLUMN_DESCRIPTIONS;
@@ -546,7 +536,8 @@ __export int osl_create_table(const struct osl_table_description *desc)
 
        if (ret < 0)
                return ret;
-       INFO_LOG("creating %s\n", desc->name);
+       t->version = CURRENT_TABLE_VERSION;
+       INFO_LOG("creating version %u table %s\n", t->version, desc->name);
        FOR_EACH_COLUMN(i, t->desc, cd) {
                if (cd->storage_type == OSL_NO_STORAGE)
                        continue;
@@ -563,6 +554,7 @@ __export int osl_create_table(const struct osl_table_description *desc)
                        if (ret < 0)
                                goto out;
                }
+               column_name_hash(t, cd->name, t->columns[i].name_hash);
                ret = -E_OSL_NOMEM;
                filename = column_filename(t, i);
                if (!filename)
@@ -729,13 +721,16 @@ int map_table(struct osl_table *t, enum map_table_flags flags)
        }
        mark_table_dirty(t);
        num_rows = table_num_rows(t);
-       if (!num_rows)
-               return num_rows;
        /* map data files */
-       FOR_EACH_MAPPED_COLUMN(i, t, cd) {
-               ret = map_column(t, i);
-               if (ret < 0)
-                       goto err;
+       FOR_EACH_COLUMN(i, t->desc, cd) {
+               if (cd->storage_type == OSL_NO_STORAGE)
+                       continue;
+               column_name_hash(t, cd->name, t->columns[i].name_hash);
+               if (num_rows > 0 && cd->storage_type == OSL_MAPPED_STORAGE) {
+                       ret = map_column(t, i);
+                       if (ret < 0)
+                               goto err;
+               }
        }
        return num_rows;
 err:   /* unmap what is already mapped */
@@ -1082,30 +1077,13 @@ int init_rbtrees(struct osl_table *t)
 __export int osl_open_table(const struct osl_table_description *table_desc,
                struct osl_table **result)
 {
-       int i, ret;
+       int ret;
        struct osl_table *t;
-       const struct osl_column_description *cd;
 
        NOTICE_LOG("opening table %s\n", table_desc->name);
        ret = init_table_structure(table_desc, &t);
        if (ret < 0)
                return ret;
-       FOR_EACH_DISK_STORAGE_COLUMN(i, t, cd) {
-               struct stat statbuf;
-               char *dirname = column_filename(t, i);
-
-               ret = -E_OSL_NOMEM;
-               if (!dirname)
-                       goto err;
-               /* check if directory exists */
-               ret = osl_stat(dirname, &statbuf);
-               free(dirname);
-               if (ret < 0)
-                       goto err;
-               ret = -E_OSL_NOTDIR;
-               if (!S_ISDIR(statbuf.st_mode))
-                       goto err;
-       }
        ret = map_table(t, MAP_TBL_FL_VERIFY_INDEX);
        if (ret < 0)
                goto err;
index bdc584b..e98c335 100644 (file)
@@ -38,6 +38,13 @@ struct osl_column {
 struct osl_table {
        /** Pointer to the table description */
        const struct osl_table_description *desc;
+       /**
+        * The CURRENT_TABLE_VERSION value of the library which created the
+        * table. This value is stored in the index header at table creation
+        * time. When the table is opened, the field is initialized from the
+        * on-disk value.
+        */
+       uint8_t version;
        /** The size of the index header of this table. */
        uint16_t index_header_size;
        /** Contains the mapping of the table's index file */
@@ -194,14 +201,7 @@ _static_inline_ size_t index_column_description_size(const char *name)
  * The version used by this instance of the library. Written to the index of
  * newly created tables.
  */
-#define CURRENT_TABLE_VERSION 1
-
-/*
- * The lowest library version that is able to use tables of version
- * CURRENT_TABLE_VERSION. Also written to the index of new tables. If
- * compat_version(table) > current_version(lib) the table can not be opened.
- */
-#define COMPAT_TABLE_VERSION 0
+#define CURRENT_TABLE_VERSION 3
 
 /*
  * The lowest table version this library understands. On open, if
@@ -456,12 +456,14 @@ _static_inline_ struct osl_row *get_row_pointer(const struct rb_node *node,
 /**
  * Compute a cryptographic hash of an osl object.
  *
+ * \param t Determines the hash function to use.
  * \param obj the Object to compute the hash value from.
  * \param hash Result is returned here.
  */
-_static_inline_ void hash_object(const struct osl_object *obj, HASH_TYPE *hash)
+_static_inline_ void hash_object(const struct osl_table *t,
+               const struct osl_object *obj, HASH_TYPE *hash)
 {
-       hash_function(obj->data, obj->size, hash);
+       hash_function(t->version, obj->data, obj->size, hash);
 }
 
 /**
diff --git a/sha1.h b/sha1.h
deleted file mode 100644 (file)
index 4d21733..0000000
--- a/sha1.h
+++ /dev/null
@@ -1,5 +0,0 @@
-/** \file sha1.h Secure Hash Algorithm prototype */
-
-/** Size of the hash value in bytes. */
-#define HASH_SIZE 20
-void sha1_hash(const char *data, unsigned long len, unsigned char *sha1);
diff --git a/sha256.c b/sha256.c
new file mode 100644 (file)
index 0000000..0732e7c
--- /dev/null
+++ b/sha256.c
@@ -0,0 +1,221 @@
+#include <inttypes.h>
+#include <arpa/inet.h>
+#include <string.h>
+
+#define blk_SHA256_BLKSIZE 64
+
+struct blk_SHA256_CTX {
+       uint32_t state[8];
+       uint64_t size;
+       uint32_t offset;
+       uint8_t buf[blk_SHA256_BLKSIZE];
+};
+
+static void blk_SHA256_Init(struct blk_SHA256_CTX *ctx)
+{
+       ctx->offset = 0;
+       ctx->size = 0;
+       ctx->state[0] = 0x6a09e667ul;
+       ctx->state[1] = 0xbb67ae85ul;
+       ctx->state[2] = 0x3c6ef372ul;
+       ctx->state[3] = 0xa54ff53aul;
+       ctx->state[4] = 0x510e527ful;
+       ctx->state[5] = 0x9b05688cul;
+       ctx->state[6] = 0x1f83d9abul;
+       ctx->state[7] = 0x5be0cd19ul;
+}
+
+static inline uint32_t ror(uint32_t x, unsigned n)
+{
+       return (x >> n) | (x << (32 - n));
+}
+
+static inline uint32_t ch(uint32_t x, uint32_t y, uint32_t z)
+{
+       return z ^ (x & (y ^ z));
+}
+
+static inline uint32_t maj(uint32_t x, uint32_t y, uint32_t z)
+{
+       return ((x | y) & z) | (x & y);
+}
+
+static inline uint32_t sigma0(uint32_t x)
+{
+       return ror(x, 2) ^ ror(x, 13) ^ ror(x, 22);
+}
+
+static inline uint32_t sigma1(uint32_t x)
+{
+       return ror(x, 6) ^ ror(x, 11) ^ ror(x, 25);
+}
+
+static inline uint32_t gamma0(uint32_t x)
+{
+       return ror(x, 7) ^ ror(x, 18) ^ (x >> 3);
+}
+
+static inline uint32_t gamma1(uint32_t x)
+{
+       return ror(x, 17) ^ ror(x, 19) ^ (x >> 10);
+}
+
+#define get_be32(p)     ntohl(*(unsigned int *)(p))
+
+static void blk_SHA256_Transform(struct blk_SHA256_CTX *ctx, const unsigned char *buf)
+{
+
+       uint32_t S[8], W[64], t0, t1;
+       int i;
+
+       /* copy state into S */
+       for (i = 0; i < 8; i++)
+               S[i] = ctx->state[i];
+
+       /* copy the state into 512-bits into W[0..15] */
+       for (i = 0; i < 16; i++, buf += sizeof(uint32_t))
+               W[i] = get_be32(buf);
+
+       /* fill W[16..63] */
+       for (i = 16; i < 64; i++)
+               W[i] = gamma1(W[i - 2]) + W[i - 7] + gamma0(W[i - 15]) + W[i - 16];
+
+#define RND(a,b,c,d,e,f,g,h,i,ki)                    \
+       t0 = h + sigma1(e) + ch(e, f, g) + ki + W[i];   \
+       t1 = sigma0(a) + maj(a, b, c);                  \
+       d += t0;                                        \
+       h  = t0 + t1;
+
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],0,0x428a2f98);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],1,0x71374491);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],2,0xb5c0fbcf);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],3,0xe9b5dba5);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],4,0x3956c25b);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],5,0x59f111f1);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],6,0x923f82a4);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],7,0xab1c5ed5);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],8,0xd807aa98);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],9,0x12835b01);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],10,0x243185be);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],11,0x550c7dc3);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],12,0x72be5d74);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],13,0x80deb1fe);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],14,0x9bdc06a7);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],15,0xc19bf174);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],16,0xe49b69c1);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],17,0xefbe4786);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],18,0x0fc19dc6);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],19,0x240ca1cc);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],20,0x2de92c6f);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],21,0x4a7484aa);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],22,0x5cb0a9dc);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],23,0x76f988da);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],24,0x983e5152);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],25,0xa831c66d);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],26,0xb00327c8);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],27,0xbf597fc7);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],28,0xc6e00bf3);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],29,0xd5a79147);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],30,0x06ca6351);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],31,0x14292967);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],32,0x27b70a85);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],33,0x2e1b2138);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],34,0x4d2c6dfc);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],35,0x53380d13);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],36,0x650a7354);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],37,0x766a0abb);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],38,0x81c2c92e);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],39,0x92722c85);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],40,0xa2bfe8a1);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],41,0xa81a664b);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],42,0xc24b8b70);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],43,0xc76c51a3);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],44,0xd192e819);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],45,0xd6990624);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],46,0xf40e3585);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],47,0x106aa070);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],48,0x19a4c116);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],49,0x1e376c08);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],50,0x2748774c);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],51,0x34b0bcb5);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],52,0x391c0cb3);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],53,0x4ed8aa4a);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],54,0x5b9cca4f);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],55,0x682e6ff3);
+       RND(S[0],S[1],S[2],S[3],S[4],S[5],S[6],S[7],56,0x748f82ee);
+       RND(S[7],S[0],S[1],S[2],S[3],S[4],S[5],S[6],57,0x78a5636f);
+       RND(S[6],S[7],S[0],S[1],S[2],S[3],S[4],S[5],58,0x84c87814);
+       RND(S[5],S[6],S[7],S[0],S[1],S[2],S[3],S[4],59,0x8cc70208);
+       RND(S[4],S[5],S[6],S[7],S[0],S[1],S[2],S[3],60,0x90befffa);
+       RND(S[3],S[4],S[5],S[6],S[7],S[0],S[1],S[2],61,0xa4506ceb);
+       RND(S[2],S[3],S[4],S[5],S[6],S[7],S[0],S[1],62,0xbef9a3f7);
+       RND(S[1],S[2],S[3],S[4],S[5],S[6],S[7],S[0],63,0xc67178f2);
+
+       for (i = 0; i < 8; i++)
+               ctx->state[i] += S[i];
+}
+
+static void blk_SHA256_Update(struct blk_SHA256_CTX *ctx, const void *data, size_t len)
+{
+       unsigned int len_buf = ctx->size & 63;
+
+       ctx->size += len;
+
+       /* Read the data into buf and process blocks as they get full */
+       if (len_buf) {
+               unsigned int left = 64 - len_buf;
+               if (len < left)
+                       left = len;
+               memcpy(len_buf + ctx->buf, data, left);
+               len_buf = (len_buf + left) & 63;
+               len -= left;
+               data = ((const char *)data + left);
+               if (len_buf)
+                       return;
+               blk_SHA256_Transform(ctx, ctx->buf);
+       }
+       while (len >= 64) {
+               blk_SHA256_Transform(ctx, data);
+               data = ((const char *)data + 64);
+               len -= 64;
+       }
+       if (len)
+               memcpy(ctx->buf, data, len);
+}
+
+#define put_be32(p, v)  do { *(unsigned int *)(p) = htonl(v); } while (0)
+
+void blk_SHA256_Final(unsigned char *digest, struct blk_SHA256_CTX *ctx)
+{
+       static const unsigned char pad[64] = { 0x80 };
+       unsigned int padlen[2];
+       int i;
+
+       /* Pad with a binary 1 (ie 0x80), then zeroes, then length */
+       padlen[0] = htonl((uint32_t)(ctx->size >> 29));
+       padlen[1] = htonl((uint32_t)(ctx->size << 3));
+
+       i = ctx->size & 63;
+       blk_SHA256_Update(ctx, pad, 1 + (63 & (55 - i)));
+       blk_SHA256_Update(ctx, padlen, 8);
+
+       /* copy output */
+       for (i = 0; i < 5; i++, digest += sizeof(uint32_t))
+               put_be32(digest, ctx->state[i]);
+}
+
+/**
+ * Compute the hash value for osl version 3 tables.
+ *
+ * \param data Pointer to the data to compute the hash value from.
+ * \param len The length of \a data in bytes.
+ * \param result must point to an area at least 20 bytes large.
+ */
+void sha256_hash(const char *data, unsigned long len, unsigned char *result)
+{
+       struct blk_SHA256_CTX c;
+
+       blk_SHA256_Init(&c);
+       blk_SHA256_Update(&c, data, len);
+       blk_SHA256_Final(result, &c);
+}
diff --git a/sha3.c b/sha3.c
new file mode 100644 (file)
index 0000000..629768c
--- /dev/null
+++ b/sha3.c
@@ -0,0 +1,149 @@
+/*
+Implementation by the Keccak, Keyak and Ketje Teams, namely, Guido Bertoni,
+Joan Daemen, MichaĆ«l Peeters, Gilles Van Assche and Ronny Van Keer, hereby
+denoted as "the implementer".
+
+For more information, feedback or questions, please refer to our websites:
+http://keccak.noekeon.org/
+http://keyak.noekeon.org/
+http://ketje.noekeon.org/
+
+To the extent possible under law, the implementer has waived all copyright
+and related or neighboring rights to the source code in this file.
+http://creativecommons.org/publicdomain/zero/1.0/
+*/
+
+#define FOR(i,n) for(i=0; i<n; ++i)
+typedef unsigned char u8;
+typedef unsigned long long int u64;
+typedef unsigned int ui;
+
+static int LFSR86540(u8 *R)
+{
+       *R = ((*R) << 1) ^ (((*R) & 0x80)? 0x71 : 0);
+       return ((*R) & 2 ) >> 1;
+}
+
+static u64 load64(const u8 *x)
+{
+       ui i;
+       u64 u = 0;
+
+       FOR(i, 8) {
+               u <<= 8;
+               u |= x[7 - i];
+       }
+       return u;
+}
+
+static void store64(u8 *x, u64 u)
+{
+       ui i;
+
+       FOR(i, 8) {
+               x[i] = u;
+               u >>= 8;
+       }
+}
+
+static void xor64(u8 *x, u64 u)
+{
+       ui i;
+       FOR(i, 8) {
+               x[i] ^= u;
+               u >>= 8;
+       }
+}
+
+#define rL(x, y) load64((u8*)s + 8 * (x + 5 * y))
+#define wL(x, y, l) store64((u8*)s + 8 * (x + 5 * y), l)
+#define XL(x, y, l) xor64((u8*)s + 8 * (x + 5 * y), l)
+#define ROL(a, o) ((((u64)a) << o) ^ (((u64)a) >> (64 - o)))
+
+static void KeccakF1600(void *s)
+{
+       ui r, x, y, i, j, Y;
+       u8 R = 0x01;
+       u64 C[5], D;
+
+       for (i = 0; i < 24; i++) {
+               FOR(x, 5)
+                       C[x] = rL(x, 0) ^ rL(x, 1) ^ rL(x, 2) ^ rL(x, 3) ^ rL(x, 4);
+               FOR(x, 5) {
+                       D = C[(x + 4) % 5] ^ ROL(C[(x + 1) % 5], 1);
+                       FOR(y, 5)
+                               XL(x, y, D);
+               }
+               x = 1;
+               y = r = 0;
+               D = rL(x, y);
+               FOR(j, 24) {
+                       r += j + 1;
+                       Y = (2 * x + 3 * y) % 5;
+                       x = y;
+                       y = Y;
+                       C[0] = rL(x, y);
+                       wL(x, y, ROL(D, r % 64));
+                       D = C[0];
+               }
+               FOR(y, 5) {
+                       FOR(x, 5)
+                               C[x] = rL(x, y);
+                       FOR(x, 5)
+                               wL(x, y, C[x] ^ ((~C[(x + 1) % 5]) & C[(x + 2) % 5]));
+               }
+               FOR(j, 7)
+                       if (LFSR86540(&R))
+                               XL(0, 0, (u64)1 << ((1 << j) - 1));
+       }
+}
+
+static void Keccak(ui r, const u8 *in, u64 inLen, u8 sfx, u8 *out, u64 outLen)
+{
+       u8 s[200];
+       ui R = r / 8;
+       ui i, b = 0;
+
+       FOR(i, 200)
+               s[i] = 0;
+       /* absorb */
+       while (inLen > 0) {
+               b = (inLen < R)? inLen : R;
+               FOR(i, b)
+                       s[i] ^= in[i];
+               in += b;
+               inLen -= b;
+               if (b == R) {
+                       KeccakF1600(s);
+                       b = 0;
+               }
+       }
+       /* pad */
+       s[b] ^= sfx;
+       if ((sfx & 0x80) && (b == (R - 1)))
+               KeccakF1600(s);
+       s[R - 1] ^= 0x80;
+       KeccakF1600(s);
+       /* squeeze */
+       while (outLen > 0) {
+               b = (outLen < R)? outLen : R;
+               FOR(i, b)
+                       out[i] = s[i];
+               out += b;
+               outLen -= b;
+               if (outLen > 0)
+                       KeccakF1600(s);
+       }
+}
+
+/**
+ * Compute the hash value for osl version 2 tables.
+ *
+ * \param data Pointer to the data to compute the hash value from.
+ * \param len The length of \a data in bytes.
+ * \param result must point to an area at least 20 bytes large.
+ */
+void sha3_hash(const char *data, unsigned long len, unsigned char *result)
+{
+        Keccak(1152, (const u8*)data, len, 0x06, result, 20);
+}