Bitcoin Forum

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define CB_BTREE_ORDER 8
#define CB_BTREE_HALF_ORDER CB_BTREE_ORDER/2

typedef struct{
	void * parent;
	void * children[CB_BTREE_ORDER + 1];
	unsigned char numElements;
} CBBTreeNode;

typedef struct{
	unsigned char found;
	CBBTreeNode * node;
	unsigned char pos;
} CBFindResult;

typedef struct{
	unsigned char keySize;
	unsigned char dataSize;
	int nodeSize;
	CBBTreeNode * root;
} CBAssociativeArray;

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key);
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right);
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize);
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize);

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key){
	CBFindResult result;
	CBBTreeNode * node = self->root;
	for (;;) {
		result = CBBTreeNodeBinarySearch(node, key, self->keySize);
		if (result.found){
			result.node = node;
			return result;
		}else{
			if (node->children[result.pos])
				node = node->children[result.pos];
			else{
				result.node = node;
				return result;
			}
		}
	}
}
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right){
	// See if we can insert data in this node
	unsigned char * keys = (unsigned char *)(pos.node + 1);
	unsigned char * dataElements = keys + self->keySize * CB_BTREE_ORDER;
	if (pos.node->numElements < CB_BTREE_ORDER) {
		if (pos.node->numElements > pos.pos){
			memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (pos.node->numElements - pos.pos) * self->keySize);
			memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (pos.node->numElements - pos.pos) * self->dataSize);
			memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (pos.node->numElements - pos.pos) *  sizeof(*pos.node->children));
		}
		memcpy(keys + pos.pos * self->keySize, key, self->keySize);
		memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
		pos.node->children[pos.pos + 1] = right;
		pos.node->numElements++;
	}else{
		CBBTreeNode * new = malloc(self->nodeSize);
		unsigned char * newKeys = (unsigned char *)(new + 1);
		unsigned char * newData = newKeys + self->keySize * CB_BTREE_ORDER;
		new->numElements = CB_BTREE_HALF_ORDER;
		pos.node->numElements = CB_BTREE_HALF_ORDER;
		unsigned char * midKey;
		unsigned char * midVal;
		if (pos.pos >= CB_BTREE_HALF_ORDER) {
			if (pos.pos == CB_BTREE_HALF_ORDER) {
				memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
				memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
				memcpy(new->children + 1, pos.node->children + CB_BTREE_HALF_ORDER + 1, CB_BTREE_HALF_ORDER * sizeof(*new->children));
				new->children[0] = right;
				midKey = key;
				midVal = data;
			}else{
				if (pos.pos > CB_BTREE_HALF_ORDER + 1){
					memcpy(newKeys, keys + (CB_BTREE_HALF_ORDER + 1) * self->keySize, (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize);
					memcpy(newData, dataElements + (CB_BTREE_HALF_ORDER + 1) * self->dataSize, (pos.pos - CB_BTREE_HALF_ORDER - 1)  * self->dataSize);
				}
				memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize, key, self->keySize);
				memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->dataSize, data, self->dataSize);
				memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_ORDER - pos.pos) * self->keySize);
				memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_ORDER - pos.pos) * self->dataSize); // o 0 i 1 ii 2 iii 3 iv
				memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER + 1, (pos.pos - CB_BTREE_HALF_ORDER) * sizeof(*new->children));
				new->children[pos.pos - CB_BTREE_HALF_ORDER] = right;
				if (CB_BTREE_ORDER > pos.pos)
					memcpy(new->children + pos.pos - CB_BTREE_HALF_ORDER + 1, pos.node->children + pos.pos + 1, (CB_BTREE_ORDER - pos.pos) * sizeof(*new->children));
				midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
				midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
			}
		}else{
			memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
			memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
			memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER, (CB_BTREE_HALF_ORDER + 1) * sizeof(*new->children));
			memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_HALF_ORDER - pos.pos) * self->keySize);
			memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_HALF_ORDER - pos.pos) * self->dataSize);
			if (CB_BTREE_HALF_ORDER > 1 + pos.pos)
				memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (CB_BTREE_HALF_ORDER - pos.pos - 1) * self->dataSize);
			memcpy(keys + pos.pos * self->keySize, key, self->keySize);
			memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
			pos.node->children[pos.pos + 1] = right;
			midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
			midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
		}
		if ( ! pos.node->parent) {
			self->root = malloc(self->nodeSize);
			self->root->numElements = 0;
			self->root->parent = NULL;
			pos.node->parent = self->root;
			self->root->children[0] = pos.node;
		}
		new->parent = pos.node->parent;
		CBFindResult res = CBBTreeNodeBinarySearch(pos.node->parent, midKey, self->keySize);
		res.node = pos.node->parent;
		return CBAssociativeArrayInsert(self, midKey, midVal, res, new);
	}
}
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize){
	CBFindResult res;
	res.found = 0;
	if ( ! self->numElements) {
		res.pos = 0;
		return res;
	}
	unsigned char left = 0;
	unsigned char right = self->numElements - 1;
	unsigned char * keys = (unsigned char *)(self + 1);
	int cmp;
	while (left <= right) {
		res.pos = (right+left)/2;
		cmp = memcmp(key, keys + res.pos * keySize, keySize);
		if (cmp == 0) {
			res.found = 1;
			break;
		}else if (cmp < 0){
			if ( ! res.pos)
				break;
			right = res.pos - 1;
		}else
			left = res.pos + 1;
	}
	if (cmp > 0)
		res.pos++;
	return res;
}
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize){
	self->keySize = keySize;
	self->dataSize = dataSize;
	self->nodeSize = sizeof(*self->root) + (keySize + dataSize) * CB_BTREE_ORDER;
	self->root = malloc(self->nodeSize);
	self->root->parent = NULL;
	self->root->numElements = 0;
	for (unsigned char x = 0; x < CB_BTREE_ORDER + 1; x++)
		self->root->children[x] = NULL;
}

int main(){
	srand(1);
	CBAssociativeArray array;
	CBInitAssociativeArray(&array, 10, 10);
	int size = CB_BTREE_ORDER * (CB_BTREE_ORDER + 2) * 10;;
	unsigned char * keys = malloc(size);
	for (int x = 0; x < size; x++) {
		keys[x] = rand();
	}
	for (int x = 0; x < size; x += 10) {
		CBAssociativeArrayInsert(&array, keys + x, keys + x, CBAssociativeArrayFind(&array, keys + x), NULL);
		for (int y = 0; y <= x; y += 10) {
			if ( ! CBAssociativeArrayFind(&array, keys + y).found) {
				printf("RANDOM FIND FAIL %u - %u\n", y, x);
				return 1;
			}
		}
	}
    return 0;
}

git clone https://github.com/MatthewLM/cbitcoin.git
cd cbitcoin
./configure
make test

==1886== Syscall param socketcall.sendto(msg) points to uninitialised byte(s)
==1886==    at 0x4E412CC: send (send.c:33)
==1886==    by 0x54881B0: CBSocketSend (CBLibEventSockets.c:287)
==1886==    by 0x506953D: CBNetworkCommunicatorOnCanSend (CBNetworkCommunicator.c:459)
==1886==    by 0x5487F43: CBCanSend (CBLibEventSockets.c:235)
==1886==    by 0x663454B: event_base_loop (event.c:1346)
==1886==    by 0x5487B29: CBStartEventLoop (CBLibEventSockets.c:154)
==1886==    by 0x4E39E99: start_thread (pthread_create.c:308)
==1886==  Address 0x6f69774 is 20 bytes inside a block of size 24 alloc'd
==1886==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1886==    by 0x506903B: CBNetworkCommunicatorOnCanSend (CBNetworkCommunicator.c:394)
==1886==    by 0x5487F43: CBCanSend (CBLibEventSockets.c:235)
==1886==    by 0x663454B: event_base_loop (event.c:1346)
==1886==    by 0x5487B29: CBStartEventLoop (CBLibEventSockets.c:154)
==1886==    by 0x4E39E99: start_thread (pthread_create.c:308)
==1886==  Uninitialised value was created by a heap allocation
==1886==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1886==    by 0x5067E55: CBNewNetworkCommunicator (CBNetworkCommunicator.c:30)
==1886==    by 0x4022C2: main (testCBNetworkCommunicator.c:286)
==1886== 
==1886== Syscall param socketcall.sendto(msg) points to uninitialised byte(s)
==1886==    at 0x4E412CC: send (send.c:33)
==1886==    by 0x54881B0: CBSocketSend (CBLibEventSockets.c:287)
==1886==    by 0x5069684: CBNetworkCommunicatorOnCanSend (CBNetworkCommunicator.c:480)
==1886==    by 0x5487F43: CBCanSend (CBLibEventSockets.c:235)
==1886==    by 0x663454B: event_base_loop (event.c:1346)
==1886==    by 0x5487B29: CBStartEventLoop (CBLibEventSockets.c:154)
==1886==    by 0x4E39E99: start_thread (pthread_create.c:308)
==1886==  Address 0x6f6918a is 106 bytes inside a block of size 110 alloc'd
==1886==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1886==    by 0x5061449: CBInitByteArrayOfSize (CBByteArray.c:133)
==1886==    by 0x5061088: CBNewByteArrayOfSize (CBByteArray.c:48)
==1886==    by 0x506C433: CBNetworkCommunicatorSendMessage (CBNetworkCommunicator.c:1307)
==1886==    by 0x506882C: CBNetworkCommunicatorDidConnect (CBNetworkCommunicator.c:217)
==1886==    by 0x5487E01: CBDidConnect (CBLibEventSockets.c:210)
==1886==    by 0x663454B: event_base_loop (event.c:1346)
==1886==    by 0x5487B29: CBStartEventLoop (CBLibEventSockets.c:154)
==1886==    by 0x4E39E99: start_thread (pthread_create.c:308)
==1886==  Uninitialised value was created by a heap allocation
==1886==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==1886==    by 0x5067E55: CBNewNetworkCommunicator (CBNetworkCommunicator.c:30)
==1886==    by 0x4022C2: main (testCBNetworkCommunicator.c:286)

bool CBGet32RandomBytes(uint8_t * bytes){
	FILE * f = fopen("/dev/random", "r");
	return fread(bytes, 1, 32, f) == 32;
}

--- ./library/dependencies/storage/CBBlockChainStorage.c        2014-03-21 19:53:02.744321264 -0400
+++ ../cbitcoin-2014-03-21/./library/dependencies/storage/CBBlockChainStorage.c 2014-03-21 01:17:12.000000000 -0400
@@ -38,7 +38,7 @@
                CBFreeIndex(self->blockHashIndex);
        }
        CBLogError("Could not load one of the block chain storage indices.");
-       CBFreeDatabase(self->database);
+       free(self);
        return false;
 }
 void CBFreeBlockChainStorage(CBDepObject self){

--- ./client-server/src/main.c  2014-03-21 19:53:02.738321373 -0400
+++ ../cbitcoin-2014-03-21/./client-server/src/main.c   2014-03-21 18:36:45.608202593 -0400
@@ -66,6 +66,9 @@
 void CBOnTransactionUnconfirmed(CBNode * node, uint8_t * txHash){
        
 }
+void CBOnUpToDate(CBNode * node, bool truefalse){
+
+}
 CBNetworkAddress * CBReadNetworkAddress(char * ipStr, bool isPublic){
        CBSocketAddress saddr = {NULL, 8333};
        char * portStart;
@@ -286,7 +289,8 @@
                CBOnNewTransaction,
                CBOnTransactionConfirmed,
                CBOnDoubleSpend,
-               CBOnTransactionUnconfirmed
+               CBOnTransactionUnconfirmed,
+               CBOnUpToDate
        };
        CBNodeFull * node = CBNewNodeFull(database, nodeFlags, otherTxsSizeLimit, callbacks);
        if (!node) {

--- ./library/dependencies/crypto/CBOpenSSLCrypto.c     2014-03-21 19:53:02.741321318 -0400
+++ ../cbitcoin-2014-03-21/./library/dependencies/crypto/CBOpenSSLCrypto.c      2014-03-21 19:44:44.181601752 -0400
@@ -84,9 +84,13 @@
        RIPEMD160(data, len, output);
 }
 bool CBEcdsaVerify(uint8_t * signature, uint8_t sigLen, uint8_t * hash, uint8_t * pubKey, uint8_t keyLen){
-       EC_KEY * key = EC_KEY_new_by_curve_name(NID_secp256k1);
+       EC_KEY *eckey, * key;
+       int res = 0;
+
+       eckey = key = EC_KEY_new_by_curve_name(NID_secp256k1);
        o2i_ECPublicKey(&key, (const unsigned char **)&pubKey, keyLen);
-       int res = ECDSA_verify(0, hash, 32, signature, sigLen, key);
-       EC_KEY_free(key);
+       if ( key != NULL )
+               res = ECDSA_verify(0, hash, 32, signature, sigLen, key);
+       EC_KEY_free(eckey);
        return res == 1;
 }