[Bitcollider-commits] CVS: bitcollider/lib kztree.c,NONE,1.1 md5.c,1.2,1.3 md5.h,1.1,1.2

[Gordon M. <go...@us...>]

Update of /cvsroot/bitcollider/bitcollider/lib
In directory sc8-pr-cvs1:/tmp/cvs-serv1165/lib

Modified Files:
	md5.c md5.h 
Added Files:
	kztree.c 
Log Message:
* kztree.c
    Kazaa tree hash support. Definition from Sharman donated code. Modelled on tigertree.c.
* md5.c, md5.h
    Add convenience MD5() procedure.

--- NEW FILE: kztree.c ---
/* (PD) 2001 The Bitzi Corporation
 * Please see file COPYING or http://bitzi.com/publicdomain 
 * for more info.
 *
 * kztree.c - Calculation of the 'KazaaTreeHash' value, which,
 * when appended to the earlier "FTHash"/"UUHash" (sig2dat)
 * value, gives the 36-byte 'kzhash' value (first used in 
 * Kazaa 2.6). 
 * 
 * 'kzhash' definition comes from example code provided and 
 * donated to the public domain by Phil Morle of Sharman 
 * Networks, 2004-01-16. 
 *
 * Adapted to allow calculation in a stream fashion -- which
 * helps calculate several hashes with only one pass through
 * an input. 
 *
 * NOTE: A tree hash value cannot be calculated using a
 * constant amount of memory for any input size;  rather,  
 * the memory required grows with the size of input. 
 * (Roughly, one more interim value must be remembered for 
 * each doubling of the input size.) The default KZTREE_CONTEXT 
 * struct size reserves enough memory for input up to 2^128 
 * bytes in length, which should be plenty. 
 *
 *
 * $Id: kztree.c,v 1.1 2004/01/18 10:59:54 gojomo Exp $
 *
 */

#include <string.h>
#include "kztree.h"
#include "md5.h"

/* 
 * Initialize the kztree context 
 */
void kztree_init(KZTREE_CONTEXT *ctx)
{
  ctx->count = 0;
  ctx->block = ctx->leaf; // working area for blocks
  ctx->index = 0;   // partial block pointer/block length
  ctx->top = ctx->nodes;
}

/* 
 * Feed given bytes into the working buffer. Whenever the buffer
 * has reached KZTREE_BLOCKSIZE, call kztree_block()
 */
void kztree_update(KZTREE_CONTEXT *ctx, unsigned char *buffer, unsigned int len)
{

  if (ctx->index)
  { /* Try to fill partial block */
	  unsigned left = KZTREE_BLOCKSIZE - ctx->index;
	  if (len < left)
		{
		memmove(ctx->block + ctx->index, buffer, len);
		ctx->index += len;
		return; /* Finished */
		}
	  else
		{
		memmove(ctx->block + ctx->index, buffer, left);
		ctx->index = KZTREE_BLOCKSIZE;
		kztree_block(ctx);
		buffer += left;
		len -= left;
		}
  }

  while (len >= KZTREE_BLOCKSIZE)
	{
	memmove(ctx->block, buffer, KZTREE_BLOCKSIZE);
	ctx->index = KZTREE_BLOCKSIZE;
	kztree_block(ctx);
	buffer += KZTREE_BLOCKSIZE;
	len -= KZTREE_BLOCKSIZE;
	}
  if ((ctx->index = len))     /* This assignment is intended */
	{
	/* Buffer leftovers */
	memmove(ctx->block, buffer, len);
	}
}

/* 
 * A full KZTREE_BLOCKSIZE bytes have become available; 
 * hash those, and possibly composite together siblings.  
 */
static void kztree_block(KZTREE_CONTEXT *ctx)
{

  MD5(ctx->leaf,ctx->index,ctx->top);
  ctx->top += MD5SIZE;
  ++ctx->count;
  ctx->gen = ctx->count; 
  while(ctx->gen == ((ctx->gen >> 1)<<1)) { // while evenly divisible by 2...
    kztree_compose(ctx);
    ctx->gen = ctx->gen >> 1;
  }
}

/* 
 * Compose the top two node values, siblings in the tree
 * structure, into a single parent node value.
 */
static void kztree_compose(KZTREE_CONTEXT *ctx) {
  unsigned char *node;
  if(ctx->gen != ((ctx->gen >> 1)<<1)) { // compose of generation with odd population
    // MD5 the only child in place
    MD5(ctx->top - MD5SIZE,MD5SIZE,ctx->top - MD5SIZE);
	return;
  }
  node = ctx->top - KZTREE_NODESIZE;
  MD5(node,(KZTREE_NODESIZE),node); // combine two nodes
  ctx->top -= MD5SIZE;              // update top ptr
}

/* 
 * 
 * no need to call this directly; kztree_digest calls it for you
 */
static void kztree_final(KZTREE_CONTEXT *ctx)
{
  // do last partial block, if any
  if(ctx->index > 0)
    kztree_block(ctx);
}

/*
 * Finish the kztree calc and return the final digest value
 */
void kztree_digest(KZTREE_CONTEXT *ctx, unsigned char *digest)
{
  kztree_final(ctx);
  while( ctx->gen > 1) {
    kztree_compose(ctx);
	ctx->gen = (ctx->gen + 1) / 2;
  }
  if( ctx->count == 1) {
	// for the single block case, hash again
	kztree_compose(ctx);
  }
  if( ctx->count == 0) {
	// for the zero-length input case, hash nothing.
	kztree_block(ctx);
  } 

  memmove(digest,ctx->nodes,MD5SIZE);
}


/*
 * Copy the context
 *
 * this code untested; use at own risk
 */ 
void kztree_copy(KZTREE_CONTEXT *dest, KZTREE_CONTEXT *src)
{
  int i;
  dest->count = src->count;
  for(i=0; i < KZTREE_BLOCKSIZE; i++)
    dest->block[i] = src->block[i];
  dest->index = src->index;
  for(i=0; i < KZTREE_STACKSIZE; i++)
    dest->nodes[i] = src->nodes[i];
  dest->top = src->top;
}

Index: md5.c
===================================================================
RCS file: /cvsroot/bitcollider/bitcollider/lib/md5.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -r1.2 -r1.3
*** md5.c	13 Aug 2001 18:38:15 -0000	1.2
--- md5.c	18 Jan 2004 10:59:54 -0000	1.3
***************
*** 19,22 ****
--- 19,26 ----
   *  - Ian Jackson <ija...@ny...>.
   * Still in the public domain.
+  *
+  * Added convenience MD5(buffer,length,digest) function. 
+  *  - Gordon Mohr <go...@bi...>
+  * Still in the public domain. 
   */
  
***************
*** 49,52 ****
--- 53,69 ----
  
  /*
+  * Convenience function for when what you need to MD5 is
+  * in a single contiguous buffer. 
+  */
+ void
+ MD5(md5byte *buffer, unsigned int length, md5byte *digest)
+ {
+ 	struct MD5Context md5ctx;
+ 	MD5Init(&md5ctx);
+ 	MD5Update(&md5ctx,buffer,length);
+ 	MD5Final(digest,&md5ctx);
+ }
+ 
+ /*
   * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
   * initialization constants.

Index: md5.h
===================================================================
RCS file: /cvsroot/bitcollider/bitcollider/lib/md5.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -r1.1 -r1.2
*** md5.h	10 Aug 2001 22:29:31 -0000	1.1
--- md5.h	18 Jan 2004 10:59:54 -0000	1.2
***************
*** 33,36 ****
--- 33,37 ----
  };
  
+ void MD5(md5byte *buffer, unsigned int length, md5byte *digest);
  void MD5Init(struct MD5Context *context);
  void MD5Update(struct MD5Context *context, md5byte const *buf, unsigned len);