From f70251b468e66cc3a39c9971017f682a56a990fd Mon Sep 17 00:00:00 2001 From: alex Date: Sun, 7 Nov 2021 15:03:31 -0800 Subject: [PATCH] ... --- inc/block.h | 3 +- inc/file.h | 2 +- src/block.c | 85 ++++++++++++----------------------------- src/file.c | 80 ++++++++++++++------------------------ test/unit/block.tests.c | 54 ++++++++++++++++---------- test/unit/file.tests.c | 44 ++++++++++++++++----- 6 files changed, 123 insertions(+), 145 deletions(-) diff --git a/inc/block.h b/inc/block.h index c426d12..8ca3d80 100644 --- a/inc/block.h +++ b/inc/block.h @@ -15,12 +15,11 @@ struct block { struct block *next; }; -int block_append_blank(struct block*); int block_duplicate(struct block**,struct block*); void block_free(struct block*); int block_init(struct block**); size_t block_length(struct block*); +int block_merkle_layer(struct block*); int block_merkle_root(struct block*); -int block_pad(struct block*); #endif diff --git a/inc/file.h b/inc/file.h index 2e029ec..2745dee 100644 --- a/inc/file.h +++ b/inc/file.h @@ -15,7 +15,7 @@ struct file { char *name; char *path; unsigned char root[crypto_hash_sha256_BYTES]; - struct block *blocks; + struct block *piece_layers; size_t size; }; diff --git a/src/block.c b/src/block.c index c8531ff..14ac30f 100644 --- a/src/block.c +++ b/src/block.c @@ -1,20 +1,5 @@ #include -static unsigned long next_power_2(unsigned long); - -int block_append_blank(struct block *p) { - if(NULL==p) { return -1; } - - while(p->next!=NULL) { - p = p->next; - } - - if(block_init(&(p->next))<0) { return -1; } - memset(p->next->hash,0,crypto_hash_sha256_BYTES); - - return 1; -} - int block_duplicate(struct block **root, struct block *to_dup) { struct block *prev, *p; if(NULL==root) { return -1; } @@ -79,72 +64,52 @@ size_t block_length(struct block *p) { return i; } -int block_merkle_root(struct block *root) { +const static unsigned char zerod[crypto_hash_sha256_BYTES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; + +int block_merkle_layer(struct block *root) { struct block *p, *to_free; crypto_hash_sha256_state state; - + if(NULL==root) { return -1; } - size_t len = block_length(root); - if(1==len) { return 0; } - if((len&(len-1))!=0) { return -1; } - p = root; while(p!=NULL) { - if(NULL==p->next) { return -1; } + if((NULL==p->next)&&(p==root)) { break; } if(hash_init(&state)<0) { return -1; } if(hash_update(&state,p->hash,crypto_hash_sha256_BYTES)<0) { return -1; } - if(hash_update(&state,p->next->hash,crypto_hash_sha256_BYTES)<0) { return -1; } - + if(p->next!=NULL) { + if(hash_update(&state,p->next->hash,crypto_hash_sha256_BYTES)<0) { return -1; } + } else { + if(hash_update(&state,zerod,crypto_hash_sha256_BYTES)<0) { return -1; } + } + if(hash_final(&state,p->hash,crypto_hash_sha256_BYTES)<0) { return -1; } - - to_free = p->next; - p->next = p->next->next; - to_free->next = NULL; - block_free(to_free); - - if(NULL==p->next) { - if(block_length(root)==1) { break; } - p = root; - continue; + to_free = p->next; + if(p->next!=NULL) { + p->next = p->next->next; + } else { + p->next = NULL; } + if(to_free!=NULL) { + to_free->next = NULL; + block_free(to_free); + } + p = p->next; } return 1; } -int block_pad(struct block *p) { - if(NULL==p) { return -1; } - - size_t i = 1; - while(p->next!=NULL) { - i++; - p = p->next; - } +int block_merkle_root(struct block *root) { + if(NULL==root) { return -1; } - size_t pad = next_power_2(i) - i; - while(pad>0) { - if(block_init(&(p->next))<0) { return -1; } - memset(p->next->hash,0,crypto_hash_sha256_BYTES); - p = p->next; - pad--; + while(root->next!=NULL) { + if(block_merkle_layer(root)<0) { return -1; } } return 1; } - -static unsigned long next_power_2(unsigned long i) { - i--; - i |= i >> 1; - i |= i >> 2; - i |= i >> 4; - i |= i >> 8; - i |= i >> 16; - i++; - - return i; -} diff --git a/src/file.c b/src/file.c index 1c04fa1..f2780d2 100644 --- a/src/file.c +++ b/src/file.c @@ -11,8 +11,8 @@ void file_free(struct file *p) { free(p->path); } - if(p->blocks!=NULL) { - block_free(p->blocks); + if(p->piece_layers!=NULL) { + block_free(p->piece_layers); } free(p); @@ -20,82 +20,60 @@ void file_free(struct file *p) { int file_hash(struct file *file_p, int piece_length) { uint8_t data[BLOCK_SIZE]; - struct block *start, *p, *next, *end; + struct block *p, *next; FILE *fp; - int blocks_per_piece; if(NULL==file_p) { return -1; } if((piece_length<16384)||(piece_length&&(piece_length&(piece_length-1)))) { return -1; } - blocks_per_piece = piece_length / BLOCK_SIZE; - fp = fopen(file_p->path,"rb"); if(NULL==fp) { perror("fopen"); return -1; } + p = NULL; while(1) { - start = NULL; - p = NULL; - for(size_t i=0;isize += len; - - if(block_init(&next)<0) { goto clean; } - if(hash(data,len,next->hash,crypto_hash_sha256_BYTES)<0) { goto clean; } - - if(NULL==p) { - start = next; - p = next; - } else { - p->next = next; - p = p->next; - } + size_t len = fread(data,sizeof(uint8_t),BLOCK_SIZE,fp); + if((len<=BLOCK_SIZE)&&(ferror(fp)!=0)) { + perror("fread"); + goto clean; } - size_t blocks = block_length(start); - if(0==blocks) { goto clean; } + if(len==0) { break; } - if(blocks!=blocks_per_piece) { - // if the file is smaller than one piece then the block hashes - // should be padded to the next power of two instead of the next - // piece boundary - if(block_pad(start)<0) { goto clean; } - } + file_p->size += len; - if(block_merkle_root(start)<0) { goto clean; } + if(block_init(&next)<0) { goto clean; } + if(hash(data,len,next->hash,crypto_hash_sha256_BYTES)<0) { goto clean; } - if(NULL==file_p->blocks) { - file_p->blocks = start; - end = start; + if(NULL==p) { + file_p->piece_layers = next; + p = next; } else { - end->next = start; - end = end->next; + p->next = next; + p = p->next; } } -done: fclose(fp); - if(block_duplicate(&start,file_p->blocks)<0) { return -1; } - if(block_pad(start)<0) { return -1; } - if(block_merkle_root(start)<0) { return -1; } - memcpy(file_p->root,start->hash,crypto_hash_sha256_BYTES); - block_free(start); + int ratio = piece_length / BLOCK_SIZE; + while(ratio>1) { + if(block_merkle_layer(file_p->piece_layers)<0) { return -1; } + ratio>>=1; + } + + if(block_duplicate(&p,file_p->piece_layers)<0) { return -1; } + if(block_merkle_root(p)<0) { goto clean; } + + memcpy(file_p->root,p->hash,crypto_hash_sha256_BYTES); + block_free(p); return 1; clean: - block_free(start); fclose(fp); return -1; } @@ -118,7 +96,7 @@ int file_init(struct file **p, const char *path) { (*p)->name = strdup(b); memset((*p)->root,0,crypto_hash_sha256_BYTES); - (*p)->blocks = NULL; + (*p)->piece_layers = NULL; (*p)->size = 0; return 1; diff --git a/test/unit/block.tests.c b/test/unit/block.tests.c index f388cbb..36804af 100644 --- a/test/unit/block.tests.c +++ b/test/unit/block.tests.c @@ -6,8 +6,8 @@ int main(); static void block_duplicate_basic_test(); static void block_init_basic_test(); static void block_length_basic_test(); +static void block_merkle_layer_basic_test(); static void block_merkle_root_basic_test(); -static void block_pad_basic_test(); int main() { setup_env(); @@ -15,8 +15,8 @@ int main() { block_init_basic_test(); block_duplicate_basic_test(); block_length_basic_test(); + block_merkle_layer_basic_test(); block_merkle_root_basic_test(); - block_pad_basic_test(); clean_env(); @@ -107,6 +107,36 @@ static void block_length_basic_test() { block_free(root); } +static void block_merkle_layer_basic_test() { + struct block *root, *p; + unsigned char expected0[crypto_hash_sha256_BYTES] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; + unsigned char expected1[crypto_hash_sha256_BYTES] = {92,133,149,95,112,146,131,236,206,43,116,241,177,85,41,24,129,159,57,9,17,129,110,123,180,102,128,90,56,171,135,243}; + unsigned char expected2[crypto_hash_sha256_BYTES] = {153,121,92,74,3,46,65,157,17,191,107,18,97,70,202,242,1,125,154,249,248,16,105,232,48,193,223,30,100,201,106,35}; + + assert(block_merkle_layer(NULL)==-1); + + assert(block_init(&root)==1); + memset(root->hash,0,crypto_hash_sha256_BYTES); + + assert(block_merkle_layer(root)==1); + assert(memcmp(root->hash,expected0,crypto_hash_sha256_BYTES)==0); + assert(root->next==NULL); + + p = root; + for(size_t i=1;i<3;i++) { + assert(block_init(&(p->next))==1); + p = p->next; + memset(p->hash,i,crypto_hash_sha256_BYTES); + } + + assert(block_merkle_layer(root)==1); + assert(memcmp(root->hash,expected1,crypto_hash_sha256_BYTES)==0); + assert(memcmp(root->next->hash,expected2,crypto_hash_sha256_BYTES)==0); + assert(NULL==root->next->next); + + block_free(root); +} + static void block_merkle_root_basic_test() { struct block *root, *p; unsigned char expected1[crypto_hash_sha256_BYTES] = {92,133,149,95,112,146,131,236,206,43,116,241,177,85,41,24,129,159,57,9,17,129,110,123,180,102,128,90,56,171,135,243}; @@ -117,7 +147,7 @@ static void block_merkle_root_basic_test() { assert(block_init(&root)==1); memset(root->hash,0,crypto_hash_sha256_BYTES); - assert(block_merkle_root(root)==0); + assert(block_merkle_root(root)==1); assert(block_init(&(root->next))==1); memset(root->next->hash,1,crypto_hash_sha256_BYTES); @@ -143,21 +173,3 @@ static void block_merkle_root_basic_test() { block_free(root); } - -static void block_pad_basic_test() { - struct block *p; - - assert(block_init(&p)==1); - assert(block_pad(p)==1); - assert(block_length(p)==1); - - assert(block_init(&(p->next))==1); - assert(block_pad(p)==1); - assert(block_length(p)==2); - - assert(block_init(&(p->next->next))==1); - assert(block_pad(p)==1); - assert(block_length(p)==4); - - block_free(p); -} diff --git a/test/unit/file.tests.c b/test/unit/file.tests.c index 1b36f88..dffe4f4 100644 --- a/test/unit/file.tests.c +++ b/test/unit/file.tests.c @@ -53,7 +53,7 @@ static void file_hash_basic_test() { assert(file_hash(p,16384)==1); assert(memcmp(p->root,expected1,crypto_hash_sha256_BYTES)==0); - assert(1==block_length(p->blocks)); + assert(1==block_length(p->piece_layers)); assert(21==p->size); file_free(p); @@ -61,7 +61,7 @@ static void file_hash_basic_test() { assert(file_init(&p,TEST_FILE_2)==1); assert(file_hash(p,16384)==1); assert(memcmp(p->root,expected2,crypto_hash_sha256_BYTES)==0); - assert(1==block_length(p->blocks)); + assert(1==block_length(p->piece_layers)); assert(26==p->size); file_free(p); @@ -69,7 +69,7 @@ static void file_hash_basic_test() { assert(file_init(&p,TEST_FILE_3)==1); assert(file_hash(p,16384)==1); assert(memcmp(p->root,expected3,crypto_hash_sha256_BYTES)==0); - assert(1==block_length(p->blocks)); + assert(1==block_length(p->piece_layers)); assert(24==p->size); file_free(p); @@ -77,7 +77,7 @@ static void file_hash_basic_test() { assert(file_init(&p,TEST_FILE_4)==1); assert(file_hash(p,16384)==1); assert(memcmp(p->root,expected4,crypto_hash_sha256_BYTES)==0); - assert(1==block_length(p->blocks)); + assert(1==block_length(p->piece_layers)); assert(51==p->size); file_free(p); @@ -85,14 +85,14 @@ static void file_hash_basic_test() { static void file_hash_large_file_test() { struct file *p; - unsigned char expected[crypto_hash_sha256_BYTES] = {58,71,55,213,6,94,65,97,113,64,176,175,139,67,229,164,13,18,213,164,166,129,202,162,224,45,9,227,191,155,144,144}; + unsigned char expected[crypto_hash_sha256_BYTES] = {100,239,196,122,239,43,229,105,216,75,220,175,222,60,41,21,90,14,137,169,54,216,172,179,234,56,139,100,139,66,216,238}; extend_file(TEST_FILE_1); assert(file_init(&p,TEST_FILE_1)==1); assert(file_hash(p,16384)==1); assert(memcmp(p->root,expected,crypto_hash_sha256_BYTES)==0); - assert(10001==block_length(p->blocks)); + assert(10001==block_length(p->piece_layers)); assert((10000*16384+21)==p->size); file_free(p); @@ -102,14 +102,38 @@ static void file_hash_large_file_test() { static void file_hash_large_piece_test() { struct file *p; - unsigned char expected[crypto_hash_sha256_BYTES] = {8,234,82,230,152,160,118,109,206,217,92,218,63,67,49,228,4,43,121,68,142,69,129,202,31,34,27,245,63,137,179,83}; + unsigned char expected[crypto_hash_sha256_BYTES] = {84,58,164,117,149,227,209,117,101,168,163,50,36,135,253,15,112,185,149,168,191,58,216,233,94,59,199,17,199,48,28,68}; extend_file(TEST_FILE_2); assert(1==file_init(&p,TEST_FILE_2)); assert(file_hash(p,32768)==1); assert(memcmp(p->root,expected,crypto_hash_sha256_BYTES)==0); - assert(5000==block_length(p->blocks)); + assert(5001==block_length(p->piece_layers)); + assert((10000*16384+26)==p->size); + + file_free(p); + + reset_env(); + + extend_file(TEST_FILE_2); + + assert(1==file_init(&p,TEST_FILE_2)); + assert(file_hash(p,65536)==1); + assert(memcmp(p->root,expected,crypto_hash_sha256_BYTES)==0); + assert(2501==block_length(p->piece_layers)); + assert((10000*16384+26)==p->size); + + file_free(p); + + reset_env(); + + extend_file(TEST_FILE_2); + + assert(1==file_init(&p,TEST_FILE_2)); + assert(file_hash(p,131072)==1); + assert(memcmp(p->root,expected,crypto_hash_sha256_BYTES)==0); + assert(1251==block_length(p->piece_layers)); assert((10000*16384+26)==p->size); file_free(p); @@ -124,7 +148,7 @@ static void file_hash_random_file_test() { assert(file_init(&p,TEST_FILE_5)==1); assert(file_hash(p,16384)==1); - assert(15625==block_length(p->blocks)); + assert(15625==block_length(p->piece_layers)); assert(256000000==p->size); file_free(p); @@ -144,7 +168,7 @@ static void file_init_basic_test() { assert(strcmp(p->path,"testdir/test")==0); memset(expected,0,crypto_hash_sha256_BYTES); assert(memcmp(p->root,expected,crypto_hash_sha256_BYTES)==0); - assert(NULL==p->blocks); + assert(NULL==p->piece_layers); assert(0==p->size); file_free(p); -- 2.39.5