SHA-256 Merkle tree: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (41 intermediate revisions by 14 users not shown) | |||
Line 5:
Implement this algorithm in your language; you can use the code from the [[SHA-256]] task for the actual hash computations. For better manageability and portability, build the tree using a smaller block size of only 1024 bytes, and demonstrate it on [https://{{SERVERNAME}}/mw/title.png the RosettaCode title image] with that block size. The final result should be the hexadecimal digest value <tt style="font-weight:bold">a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c</tt>.
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/* program merkleRoot64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
.equ O_RDWR, 0x0002 // open for reading and writing
.equ BUFFERSIZE, 65535 // file buffer
.equ LGBLOCK, 1024 // block length
.equ LGHASH, 32 // hash length
.equ NBELEMENTS, 40 // array size
.equ LGZONETRAV, 2048 // process array size
/*******************************************/
/* Structures */
/********************************************/
/* structure variables hash compute */
.struct 0
var_a: // a
.struct var_a + 4
var_b: // b
.struct var_b + 4
var_c: // c
.struct var_c + 4
var_d: // d
.struct var_d + 4
var_e: // e
.struct var_e + 4
var_f: // f
.struct var_f + 4
var_g: // g
.struct var_g + 4
var_h: // h
.struct var_h + 4
/***********************************/
/* Initialized data */
/***********************************/
.data
szFileName: .asciz "title.png"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "Error detected.\n"
szMessNbHash: .asciz "Start hash number : @ \n"
szMessTest: .asciz "Rosetta code"
.align 4
/* array constantes Hi */
tbConstHi: .int 0x6A09E667 // H0
.int 0xBB67AE85 // H1
.int 0x3C6EF372 // H2
.int 0xA54FF53A // H3
.int 0x510E527F // H4
.int 0x9B05688C // H5
.int 0x1F83D9AB // H6
.int 0x5BE0CD19 // H7
/* array 64 constantes Kt */
tbConstKt:
.int 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5
.int 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174
.int 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da
.int 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967
.int 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85
.int 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070
.int 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3
.int 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
/***********************************/
/* UnInitialized data */
/***********************************/
.bss
sBuffer: .skip BUFFERSIZE // file buffer
.align 8
qNbBlocs: .skip 8
qNbHash: .skip 8
sZoneConv: .skip 24
sZoneTrav: .skip LGZONETRAV
HashResult: .skip LGHASH + 8
HashProcess: .skip LGHASH * 2
tbListHash: .skip LGHASH * NBELEMENTS
tbH: .skip 4 * 8 // 8 variables H
tbabcdefgh: .skip 4 * 8
tbW: .skip 4 * 64 // 64 words W
/***********************************/
/* code section */
/***********************************/
.text
.global main
main:
mov x0,AT_FDCWD // current directory
ldr x1,qAdrszFileName // File name
mov x2,#O_RDWR // flags
mov x3,#0 // mode
mov x8,#OPEN // open file
svc #0
cmp x0,#0 // error ?
ble error
mov x19,x0 // save fd
ldr x1,qAdrsBuffer
mov x2,#BUFFERSIZE
mov x8,#READ // call system read file
svc 0
cmp x0,#0 // error read ?
ble error
mov x7,x0 // number of read characters
ldr x6,qAdrsBuffer
mov x5,#0 // counter characters block
1:
add x0,x6,x5 // start address of each block
ldr x1,qAdrHashResult
mov x2,#LGBLOCK
bl computeSHA256LG
bl storeHash // store hash in start array
cmp x0,#-1
beq error
add x5,x5,#LGBLOCK // new buffer offset
sub x0,x7,x5 //
cmp x0,#LGBLOCK // last block
bge 1b // and loop
sub x2,x7,x5 // length last block
add x0,x6,x5 // address last block
ldr x1,qAdrHashResult
bl computeSHA256LG
bl storeHash
cmp x0,#-1
beq error
ldr x0,qAdrqNbHash
ldr x0,[x0]
ldr x1,qAdrsZoneConv
bl conversion10
ldr x0,qAdrszMessNbHash
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc
bl affichageMess
ldr x0,qAdrtbListHash
ldr x1,qAdrHashResult
bl calculerMerkleRoot
ldr x0,qAdrHashResult
bl displaySHA256 // display résult
end:
mov x0,x19 // FD
mov x8, #CLOSE // call system close file
svc #0
cmp x0,#0
blt error
mov x0,#0 // return code
b 100f
error:
ldr x0,qAdrszMessErreur // error message
bl affichageMess
mov x0,#1 // return error code
100: // standard end of the program
mov x8, #EXIT // request to exit program
svc 0 // perform system call
qAdrsBuffer: .quad sBuffer
qAdrszFileName: .quad szFileName
qAdrszMessErreur: .quad szMessErreur
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrHashResult: .quad HashResult
qAdrszMessNbHash: .quad szMessNbHash
qAdrszMessTest: .quad szMessTest
/******************************************************************/
/* store hash in start array */
/******************************************************************/
/* x0 hash address */
storeHash:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
ldr x2,qAdrqNbHash // number element counter
ldr x3,[x2]
ldr x1,qAdrtbListHash // address array hash
mov x4,#LGHASH // hash length
madd x5,x4,x3,x1 // compute store address
mov x1,#0 // counter
1:
ldr w4,[x0,x1] // load four bytes
str w4,[x5,x1] // store four bytes
add x1,x1,#4
cmp x1,#LGHASH // 32 bytes ?
blt 1b // no -> loop
add x3,x3,#1
cmp x3,#NBELEMENTS
bge 99f // error
str x3,[x2] // store new counter hash
b 100f
99:
mov x0,#-1 // error ?
100:
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrqNbHash: .quad qNbHash
qAdrtbListHash: .quad tbListHash
/******************************************************************/
/* compute hash root Merkle */
/******************************************************************/
// x0 start array hash address
// x1 result array address (32 bytes)
calculerMerkleRoot:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x10,x1
mov x12,sp // save stack adresse
ldr x3,qAdrqNbHash
ldr x3,[x3]
cmp x3,#0 // 0 hash ?
beq 99f // error
mov x4,#LGHASH * 2
mul x1,x3,x4 // compute hash size * blocks number * 2
sub sp,sp,x1 // reserve array
mov fp,sp // address previousTreeLayer
lsr x1,x1,#1 // reserve size / 2
add x7,fp,x1 // address TreeLayer
mov x2,#0 // counter
mov x4,#LGHASH
1:
mul x1,x2,x4
add x6,x0,x1
add x8,fp,x1
mov x5,#0
2: // loop copying 32 octets hash
ldr w9,[x6,x5]
str w9,[x8,x5]
add x5,x5,#4 // count
cmp x5,#LGHASH
blt 2b
add x2,x2,#1 // next hash block
cmp x2,x3 // maxi ?
blt 1b
mov x0,fp
mov x11,#0 // indice TreeLayer
mov x5,#0 // indice layer
3: // loop
cmp x3,#1 // one hash ?
beq 12f // yes -> end
sub x3,x3,#1
mov x4,#LGHASH
madd x8,x11,x4,fp // address hash 1
mov x9,x7 // raz TreeLayer
4:
cmp x11,x3
bgt 11f // end loop ?
blt 5f
mov x0,x8 // last odd hash
add x11,x11,#1 // no concatenation
mov x1,#0
41: // but loop copy odd hash in treelayer
ldr w4,[x0,x1]
str w4,[x9,x1]
add x1,x1,#4
cmp x1,#LGHASH
blt 41b
b 9f
5: // other hashes
add x6,x8,#LGHASH // address hash N + 1
6:
add x11,x11,#1
ldr x1,qAdrHashProcess // address array hash concatenation
mov x0,#0
7: // loop copy element N
ldr w4,[x8,x0]
rev w4,w4 // inversion byte in word
str w4,[x1,x0]
add x0,x0,#4
cmp x0,#LGHASH
blt 7b
add x1,x1,#LGHASH
mov x0,#0
8: // loop copy element N + 1
ldr w4,[x6,x0]
rev w4,w4 // inversion byte in word
str w4,[x1,x0]
add x0,x0,#4
cmp x0,#LGHASH
blt 8b
ldr x0,qAdrHashProcess
mov x1,x9
mov x2,#LGHASH * 2
bl computeSHA256LG // calcul du hash complet
9:
add x11,x11,#1 // incremente counter previousTreeLayer
add x5,x5,#1 // incremente counter treeLayer
add x9,x9,#LGHASH // next address treeLayer
add x8,x6,#LGHASH // maj element N avec N + 2
b 4b
11:
mov x0,fp
mov fp,x7 // treelayer in previous
mov x7,x0
mov x3,x5 // counter previous = counter treelayer
mov x5,#0 // raz treelayer
mov x11,#0 // raz previousTreeLayer
b 3b // and loop
12: // end process
mov x1,fp
mov x2,#0
13: // loop copy result
ldr w3,[x1,x2]
str w3,[x10,x2]
add x2,x2,#4
cmp x2,#LGHASH
blt 13b
mov x0,x10 // return address result
b 100f
99: // error
mov x0,#-1
100:
mov sp,x12 // restaur stack
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret
qAdrHashProcess: .quad HashProcess
/******************************************************************/
/* compute SHA256 avec longueur */
/******************************************************************/
/* x0 contains the string address */
/* x1 contains the return area address */
/* x2 contains string length */
computeSHA256LG:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
stp x4,x5,[sp,-16]! // save registers
stp x6,x7,[sp,-16]! // save registers
stp x8,x9,[sp,-16]! // save registers
stp x10,x11,[sp,-16]! // save registers
stp x12,x13,[sp,-16]! // save registers
stp x19,x20,[sp,-16]! // save registers
mov x19,x1
ldr x1,qAdrtbH
mov x3,0
1: // modif 12/11/2021 boucle raz des 3 zones
str xzr,[x1,x3,lsl 3]
add x3,x3,1
cmp x3,4+4+32
blt 1b
ldr x1,qAdrsZoneTrav
mov x3,0
2: // modif 12/11/2021 boucle raz zone de travail
str xzr,[x1,x3,lsl 3]
add x3,x3,1
cmp x3,LGZONETRAV/8
blt 2b
mov x5,x2
mov x2,#0 // counter length
debCopy: // copy string in work area
ldrb w3,[x0,x2]
strb w3,[x1,x2]
cmp x2,x5 // modification 21/11/2021
add x4,x2,1
csel x2,x4,x2,ne
bne debCopy
//affmemtit copieSH x1 3
//affregtit copie 0
lsl x6,x2,#3 // initial message length in bits
mov x3,#0b10000000 // add bit 1 at end of string
strb w3,[x1,x2]
//affmemtit copieSH1 x1 3
add x2,x2,#1 // length in bytes
lsl x4,x2,#3 // length in bits
mov x3,#0
addZeroes:
lsr x5,x2,#6
lsl x5,x5,#6
sub x5,x2,x5
cmp x5,#56
beq storeLength // yes -> end add
strb w3,[x1,x2] // add zero at message end
add x2,x2,#1 // increment lenght bytes
add x4,x4,#8 // increment length in bits
b addZeroes
storeLength:
add x2,x2,#4 // add four bytes
rev w6,w6 // inversion bits initials message length
str w6,[x1,x2] // and store at end
ldr x7,qAdrtbConstHi // constantes H address
ldr x4,qAdrtbH // start area H
mov x5,#0
loopConst: // init array H with start constantes
ldr w6,[x7,x5,lsl #2] // load constante
str w6,[x4,x5,lsl #2] // and store
add x5,x5,#1
cmp x5,#8
blt loopConst
// split into block of 64 bytes
add x2,x2,#4 //
lsr x4,x2,#6 // blocks number
ldr x0,qAdrqNbBlocs
str x4,[x0] // save block maxi
mov x7,#0 // n° de block et x1 contient l adresse zone de travail
loopBlock: // begin loop of each block of 64 bytes
mov x0,x7
bl inversion // inversion each word because little indian
ldr x3,qAdrtbW // working area W address
mov x6,#0 // indice t
/* x2 address begin each block */
ldr x1,qAdrsZoneTrav
add x2,x1,x7,lsl #6 // compute block begin indice * 4 * 16
//mov x0,x2
//affmemtit verifBloc x0 10
loopPrep: // loop for expand 80 words
cmp x6,#15 //
bgt expand1
ldr w0,[x2,x6,lsl #2] // load word message
str w0,[x3,x6,lsl #2] // store in first 16 block
b expandEnd
expand1:
sub x8,x6,#2
ldr w9,[x3,x8,lsl #2]
ror w10,w9,#17 // fonction e1 (256)
ror w11,w9,#19
eor w10,w10,w11
lsr w11,w9,#10
eor w10,w10,w11
sub x8,x6,#7
ldr w9,[x3,x8,lsl #2]
add w9,w9,w10 // + w - 7
sub x8,x6,#15
ldr w10,[x3,x8,lsl #2]
ror w11,w10,#7 // fonction e0 (256)
ror w12,w10,#18
eor w11,w11,w12
lsr w12,w10,#3
eor w10,w11,w12
add w9,w9,w10
sub x8,x6,#16
ldr w11,[x3,x8,lsl #2]
add w9,w9,w11
str w9,[x3,x6,lsl #2]
expandEnd:
add x6,x6,#1
cmp x6,#64 // 64 words ?
blt loopPrep // and loop
/* COMPUTING THE MESSAGE DIGEST */
/* x1 area H constantes address */
/* x3 working area W address */
/* x5 address constantes K */
/* x6 counter t */
/* x7 block counter */
/* x8 addresse variables a b c d e f g h */
//ldr x0,qAdrtbW
//affmemtit verifW80 x0 20
// init variable a b c d e f g h
ldr x0,qAdrtbH
//affmemtit veriftbh x0 20
ldr x8,qAdrtbabcdefgh
mov x1,#0
loopInita:
ldr w9,[x0,x1,lsl #2]
str w9,[x8,x1,lsl #2]
add x1,x1,#1
cmp x1,#8
blt loopInita
ldr x1,qAdrtbConstHi
ldr x5,qAdrtbConstKt
mov x6,#0
loop64T: // begin loop 64 t
ldr w9,[x8,#var_h]
ldr w10,[x8,#var_e] // calcul T1
ror w11,w10,#6 // fonction sigma 1
ror w12,w10,#11
eor w11,w11,w12
ror w12,w10,#25
eor w11,w11,w12
add w9,w9,w11 // h + sigma1 (e)
ldr w0,[x8,#var_f] // fonction ch x and y xor (non x and z)
ldr w4,[x8,#var_g]
and w11,w10,w0
mvn w12,w10
and w12,w12,w4
eor w11,w11,w12
add w9,w9,w11 // h + sigma1 (e) + ch (e,f,g)
ldr w0,[x5,x6,lsl #2] // load constantes k0
add w9,w9,w0
ldr w0,[x3,x6,lsl #2] // Wt
add w9,w9,w0
// calcul T2
ldr w10,[x8,#var_a] // fonction sigma 0
ror w11,w10,#2
ror w12,w10,#13
eor w11,w11,w12
ror w12,w10,#22
eor w11,w11,w12
ldr w2,[x8,#var_b]
ldr w4,[x8,#var_c]
// fonction maj x and y xor x and z xor y and z
and w12,w10,w2
and w0,w10,w4
eor w12,w12,w0
and w0,w2,w4
eor w12,w12,w0 //
add w12,w12,w11 // T2
// compute variables
ldr w4,[x8,#var_g]
str w4,[x8,#var_h]
ldr w4,[x8,#var_f]
str w4,[x8,#var_g]
ldr w4,[x8,#var_e]
str w4,[x8,#var_f]
ldr w4,[x8,#var_d]
add w4,w4,w9 // add T1
str w4,[x8,#var_e]
ldr w4,[x8,#var_c]
str w4,[x8,#var_d]
ldr w4,[x8,#var_b]
str w4,[x8,#var_c]
ldr w4,[x8,#var_a]
str w4,[x8,#var_b]
add w4,w9,w12 // add T1 T2
str w4,[x8,#var_a]
add x6,x6,#1 // increment t
cmp x6,#64
blt loop64T
// End block
ldr x0,qAdrtbH // start area H
mov x10,#0
loopStoreH:
ldr w9,[x8,x10,lsl #2]
ldr w3,[x0,x10,lsl #2]
add w3,w3,w9
str w3,[x0,x10,lsl #2] // store variables in H0
add x10,x10,#1
cmp x10,#8
blt loopStoreH
// other bloc
add x7,x7,#1 // increment block
ldr x0,qAdrqNbBlocs
ldr x4,[x0] // restaur maxi block
cmp x7,x4 // maxi ?
blt loopBlock // loop other block
ldr x0,qAdrtbH // adresse resultat
//affmemtit resultat x0 3
mov x3,0
loopRes: // boucle de copie du hash
ldr w1,[x0,x3] // dans zone de retour
str w1,[x19,x3]
add x3,x3,4
cmp x3,28
ble loopRes
mov x0,x19
100:
ldp x19,x20,[sp],16 // restaur 2 registers
ldp x12,x13,[sp],16 // restaur 2 registers
ldp x10,x11,[sp],16 // restaur 2 registers
ldp x8,x9,[sp],16 // restaur 2 registers
ldp x6,x7,[sp],16 // restaur 2 registers
ldp x4,x5,[sp],16 // restaur 2 registers
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrsZoneTrav: .quad sZoneTrav
qAdrtbConstHi: .quad tbConstHi
qAdrtbConstKt: .quad tbConstKt
qAdrtbH: .quad tbH
qAdrtbW: .quad tbW
qAdrtbabcdefgh: .quad tbabcdefgh
qAdrqNbBlocs: .quad qNbBlocs
/******************************************************************/
/* inversion des mots de 32 bits d un bloc */
/******************************************************************/
/* x0 contains N° block */
inversion:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
ldr x1,qAdrsZoneTrav
add x1,x1,x0,lsl #6 // debut du bloc
mov x2,#0
1: // start loop
ldr w3,[x1,x2,lsl #2]
rev w3,w3
str w3,[x1,x2,lsl #2]
add x2,x2,#1
cmp x2,#16
blt 1b
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* display hash SHA1 */
/******************************************************************/
/* x0 contains the address of hash */
/* x1 contains the address of recept zone */
conversionSHA256:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x3,x0
mov x2,#0
1:
ldr w0,[x3,x2,lsl #2] // load 4 bytes
//rev x0,x0 // reverse bytes
bl conversion16_4W // conversion hexa
add x1,x1,8
add x2,x2,#1
cmp x2,#LGHASH / 4
blt 1b // and loop
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
/******************************************************************/
/* display hash SHA1 */
/******************************************************************/
/* x0 contains the address of hash */
displaySHA256:
stp x1,lr,[sp,-16]! // save registers
stp x2,x3,[sp,-16]! // save registers
mov x3,x0
mov x2,#0
1:
ldr w0,[x3,x2,lsl #2] // load 4 bytes
//rev x0,x0 // reverse bytes
ldr x1,qAdrsZoneConv
bl conversion16_4W // conversion hexa
ldr x0,qAdrsZoneConv
bl affichageMess
add x2,x2,#1
cmp x2,#LGHASH / 4
blt 1b // and loop
ldr x0,qAdrszCarriageReturn
bl affichageMess // display message
100:
ldp x2,x3,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // return to address lr x30
qAdrsZoneConv: .quad sZoneConv
/******************************************************************/
/* conversion hexadecimal register 32 bits */
/******************************************************************/
/* x0 contains value and x1 address zone receptrice */
conversion16_4W:
stp x0,lr,[sp,-48]! // save registres
stp x1,x2,[sp,32] // save registres
stp x3,x4,[sp,16] // save registres
mov x2,#28 // start bit position
mov x4,#0xF0000000 // mask
mov x3,x0 // save entry value
1: // start loop
and x0,x3,x4 // value register and mask
lsr x0,x0,x2 // right shift
cmp x0,#10 // >= 10 ?
bge 2f // yes
add x0,x0,#48 // no is digit
b 3f
2:
add x0,x0,#55 // else is a letter A-F
3:
strb w0,[x1],#1 // load result and + 1 in address
lsr x4,x4,#4 // shift mask 4 bits left
subs x2,x2,#4 // decrement counter 4 bits <= zero ?
bge 1b // no -> loop
100: // fin standard de la fonction
ldp x3,x4,[sp,16] // restaur des 2 registres
ldp x1,x2,[sp,32] // restaur des 2 registres
ldp x0,lr,[sp],48 // restaur des 2 registres
ret
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Start hash number : 22
A4F902CF9D51FE51EDA156A6792E1445DFF65EDF3A217A1F3334CC9CF1495C2C
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program merkleRoot.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10
see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes */
/************************************/
.include "../constantes.inc"
.equ READ, 3
.equ OPEN, 5
.equ O_RDWR, 0x0002 @ open for reading and writing
.equ BUFFERSIZE, 65535 @ file buffer
.equ LGBLOCK, 1024 @ block length
.equ LGHASH, 32 @ hash length
.equ NBELEMENTS, 40 @ array size
.equ LGZONETRAV, 2048 @ process array size
/*******************************************/
/* Structures */
/********************************************/
/* structure variables hash compute */
.struct 0
var_a: @ a
.struct var_a + 4
var_b: @ b
.struct var_b + 4
var_c: @ c
.struct var_c + 4
var_d: @ d
.struct var_d + 4
var_e: @ e
.struct var_e + 4
var_f: @ f
.struct var_f + 4
var_g: @ g
.struct var_g + 4
var_h: @ h
.struct var_h + 4
/* structure linkedlist*/
.struct 0
@llist_next: @ next element
@ .struct llist_next + 4
@llist_value: @ element value
@ .struct llist_value + 4
@llist_fin:
/***********************************/
/* Initialized data */
/***********************************/
.data
szFileName: .asciz "title.png"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "Error detected.\n"
szMessNbHash: .asciz "Start hash number : @ \n"
.align 4
/* array constantes Hi */
tbConstHi: .int 0x6A09E667 @ H0
.int 0xBB67AE85 @ H1
.int 0x3C6EF372 @ H2
.int 0xA54FF53A @ H3
.int 0x510E527F @ H4
.int 0x9B05688C @ H5
.int 0x1F83D9AB @ H6
.int 0x5BE0CD19 @ H7
/* array 64 constantes Kt */
tbConstKt:
.int 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5
.int 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174
.int 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da
.int 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967
.int 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85
.int 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070
.int 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3
.int 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
/***********************************/
/* UnInitialized data */
/***********************************/
.bss
sBuffer: .skip BUFFERSIZE @ file buffer
.align 4
iNbBlocs: .skip 4
iNbHash: .skip 4
sZoneConv: .skip 24
sZoneTrav: .skip LGZONETRAV
HashResult: .skip LGHASH + 4
HashProcess: .skip LGHASH * 2
.align 8
tbListHash: .skip LGHASH * NBELEMENTS
tbH: .skip 4 * 8 @ 8 variables H
tbabcdefgh: .skip 4 * 8
tbW: .skip 4 * 64 @ 64 words W
/***********************************/
/* code section */
/***********************************/
.text
.global main
main:
ldr r0,iAdrszFileName @ File name
mov r1,#O_RDWR @ flags
mov r2,#0 @ mode
mov r7,#OPEN @ open file
svc #0
cmp r0,#0 @ error ?
ble error
mov r12,r0 @ save fd
ldr r1,iAdrsBuffer
mov r2,#BUFFERSIZE
mov r7,#READ @ call system read file
svc 0
cmp r0,#0 @ error read ?
ble error
mov r7,r0 @ number of read characters
ldr r6,iAdrsBuffer
mov r5,#0 @ counter characters block
1:
add r0,r6,r5 @ start address of each block
mov r1,#LGBLOCK
bl computeSHA256
bl storeHash @ store hash in start array
cmp r0,#-1
beq error
add r5,#LGBLOCK @ new buffer offset
sub r0,r7,r5 @
cmp r0,#LGBLOCK @ last block
bge 1b @ and loop
sub r1,r7,r5 @ length last block
add r0,r6,r5 @ address last block
bl computeSHA256
bl storeHash
cmp r0,#-1
beq error
ldr r0,iAdriNbHash
ldr r0,[r0]
ldr r1,iAdrsZoneConv
bl conversion10
ldr r0,iAdrszMessNbHash
ldr r1,iAdrsZoneConv
bl strInsertAtCharInc
bl affichageMess
ldr r0,iAdrtbListHash
ldr r1,iAdrHashResult
bl calculerMerkleRoot
ldr r0,iAdrHashResult
bl displaySHA256 @ display résult
end:
mov r0,r12 @ FD
mov r7, #CLOSE @ call system close file
svc #0
cmp r0,#0
blt error
mov r0,#0 @ return code
b 100f
error:
ldr r1,iAdrszMessErreur @ error message
bl displayError
mov r0,#1 @ return error code
100: @ standard end of the program
mov r7, #EXIT @ request to exit program
svc 0 @ perform system call
iAdrsBuffer: .int sBuffer
iAdrszFileName: .int szFileName
iAdrszMessErreur: .int szMessErreur
iAdrszCarriageReturn: .int szCarriageReturn
iAdrHashResult: .int HashResult
iAdrszMessNbHash: .int szMessNbHash
/******************************************************************/
/* store hash in start array */
/******************************************************************/
/* r0 hash address */
storeHash:
push {r1-r5,lr}
ldr r2,iAdriNbHash @ number element counter
ldr r3,[r2]
ldr r1,iAdrtbListHash @ address array hash
mov r4,#LGHASH @ hash length
mla r5,r4,r3,r1 @ compute store address
mov r1,#0 @ counter
1:
ldr r4,[r0,r1] @ load four bytes
str r4,[r5,r1] @ store four bytes
add r1,#4
cmp r1,#LGHASH @ 32 bytes ?
blt 1b @ no -> loop
add r3,#1
cmp r3,#NBELEMENTS
movge r0,#-1 @ error ?
bge 100f
str r3,[r2] @ store new counter hash
100:
pop {r1-r5,lr} @ restaur registers
bx lr
iAdriNbHash: .int iNbHash
iAdrtbListHash: .int tbListHash
/******************************************************************/
/* compute hash root Merkle */
/******************************************************************/
@ r0 start array hash address
@ r1 result array address (32 bytes)
calculerMerkleRoot:
push {r1-r12,lr} @ save registers
mov r10,r1
mov r12,sp @ save stack adresse
ldr r3,iAdriNbHash
ldr r3,[r3]
cmp r3,#0 @ 0 hash ?
moveq r0,#-1 @ error
beq 100f
mov r4,#LGHASH * 2
mul r1,r3,r4 @ compute hash size * blocks number * 2
sub sp,sp,r1 @ reserve array
mov fp,sp @ address previousTreeLayer
lsr r1,#1 @ reserve size / 2
add r7,fp,r1 @ address TreeLayer
mov r2,#0 @ counter
mov r4,#LGHASH
1:
mul r1,r2,r4
add r6,r0,r1
add r8,fp,r1
mov r5,#0
2: @ loop copying 32 octets hash
ldr r9,[r6,r5]
str r9,[r8,r5]
add r5,r5,#4 @ count
cmp r5,#LGHASH
blt 2b
add r2,#1 @ next hash block
cmp r2,r3 @ maxi ?
blt 1b
mov r0,fp
mov r2,#0 @ indice TreeLayer
mov r5,#0 @ indice layer
3: @ loop
cmp r3,#1 @ one hash ?
beq 12f @ yes -> end
sub r3,#1
mov r4,#LGHASH
mla r8,r2,r4,fp @ address hash 1
mov r9,r7 @ raz TreeLayer
4:
cmp r2,r3
bgt 11f @ end loop ?
blt 5f
mov r0,r8 @ last odd hash
add r2,#1 @ no concatenation
b 9f
5: @ other hashes
add r6,r8,#LGHASH @ address hash N + 1
6:
add r2,#1
ldr r1,iAdrHashProcess @ address array hash concatenation
mov r0,#0
7: @ loop copy element N
ldr r4,[r8,r0]
rev r4,r4 @ inversion byte in word
str r4,[r1,r0]
add r0,r0,#4
cmp r0,#LGHASH
blt 7b
add r1,r1,#LGHASH
mov r0,#0
8: @ loop copy element N + 1
ldr r4,[r6,r0]
rev r4,r4 @ inversion byte in word
str r4,[r1,r0]
add r0,r0,#4
cmp r0,#LGHASH
blt 8b
ldr r0,iAdrHashProcess
mov r1,#LGHASH * 2
bl computeSHA256 @ calcul du hash complet
9:
mov r1,#0
10: @ loop copy hash in treelayer
ldr r4,[r0,r1]
str r4,[r9,r1]
add r1,r1,#4
cmp r1,#LGHASH
blt 10b
mov r1,r9
add r2,r2,#1 @ incremente counter previousTreeLayer
add r5,r5,#1 @ incremente counter treeLayer
add r9,#LGHASH @ next address treeLayer
add r8,r6,#LGHASH @ maj element N avec N + 2
b 4b
11:
mov r0,fp
mov fp,r7 @ treelayer in previous
mov r7,r0
mov r3,r5 @ counter previous = counter treelayer
mov r5,#0 @ raz treelayer
mov r2,#0 @ raz previousTreeLayer
b 3b @ and loop
12: @ end process
mov r1,fp
mov r2,#0
13: @ loop copy result
ldr r3,[r1,r2]
str r3,[r10,r2]
add r2,r2,#4
cmp r2,#LGHASH
blt 13b
mov r0,r10 @ return address result
b 100f
99: @ error
mov r0,#-1
100:
mov sp,r12 @ restaur stack
pop {r1-r12,lr} @ restaur registers
bx lr @ return
iAdrHashProcess: .int HashProcess
/******************************************************************/
/* compute SHA1 */
/******************************************************************/
/* r0 contains the address of the message */
/* r1 contains string length */
computeSHA256:
push {r1-r12,lr} @ save registres
mov r5,r1 @ counter length
ldr r1,iAdrtbH
mov r3,#0
mov r4,#0
razTB:
str r4,[r1,r3]
add r3,#4
cmp r3,#8 + 8 + 64
blt razTB
ldr r1,iAdrsZoneTrav
mov r3,#0
mov r4,#0
razZone:
str r4,[r1,r3]
add r3,#4
cmp r3,#LGZONETRAV
blt razZone
@vidregtit apresraz
mov r2,#0
debCopy: @ copy string in work area
ldrb r3,[r0,r2]
strb r3,[r1,r2]
cmp r2,r5
addne r2,r2,#1
bne debCopy
@vidregtit aprescopie
lsl r6,r2,#3 @ initial message length in bits
mov r3,#0b10000000 @ add bit 1 at end of string
strb r3,[r1,r2]
add r2,r2,#1 @ length in bytes
lsl r4,r2,#3 @ length in bits
mov r3,#0
addZeroes:
lsr r5,r2,#6
lsl r5,r5,#6
sub r5,r2,r5
cmp r5,#56
beq storeLength @ yes -> end add
strb r3,[r1,r2] @ add zero at message end
add r2,#1 @ increment lenght bytes
add r4,#8 @ increment length in bits
b addZeroes
storeLength:
add r2,#4 @ add four bytes
rev r6,r6 @ inversion bits initials message length
str r6,[r1,r2] @ and store at end
ldr r7,iAdrtbConstHi @ constantes H address
ldr r4,iAdrtbH @ start area H
mov r5,#0
loopConst: @ init array H with start constantes
ldr r6,[r7,r5,lsl #2] @ load constante
str r6,[r4,r5,lsl #2] @ and store
add r5,r5,#1
cmp r5,#8
blt loopConst
@ split into block of 64 bytes
add r2,#4 @ TODO : à revoir
lsr r4,r2,#6 @ blocks number
ldr r0,iAdriNbBlocs
str r4,[r0] @ save block maxi
mov r7,#0 @ n° de block et r1 contient l adresse zone de travail
loopBlock: @ begin loop of each block of 64 bytes
mov r0,r7
bl inversion @ inversion each word because little indian
ldr r3,iAdrtbW @ working area W address
mov r6,#0 @ indice t
/* r2 address begin each block */
ldr r1,iAdrsZoneTrav
add r2,r1,r7,lsl #6 @ compute block begin indice * 4 * 16
@vidregtit avantloop
@mov r0,r2
@vidmemtit verifBloc r0 10
loopPrep: @ loop for expand 80 words
cmp r6,#15 @
bgt expand1
ldr r0,[r2,r6,lsl #2] @ load byte message
str r0,[r3,r6,lsl #2] @ store in first 16 block
b expandEnd
expand1:
sub r8,r6,#2
ldr r9,[r3,r8,lsl #2]
ror r10,r9,#17 @ fonction e1 (256)
ror r11,r9,#19
eor r10,r10,r11
lsr r11,r9,#10
eor r10,r10,r11
sub r8,r6,#7
ldr r9,[r3,r8,lsl #2]
add r9,r9,r10 @ + w - 7
sub r8,r6,#15
ldr r10,[r3,r8,lsl #2]
ror r11,r10,#7 @ fonction e0 (256)
ror r12,r10,#18
eor r11,r12
lsr r12,r10,#3
eor r10,r11,r12
add r9,r9,r10
sub r8,r6,#16
ldr r11,[r3,r8,lsl #2]
add r9,r9,r11
str r9,[r3,r6,lsl #2]
expandEnd:
add r6,r6,#1
cmp r6,#64 @ 64 words ?
blt loopPrep @ and loop
/* COMPUTING THE MESSAGE DIGEST */
/* r1 area H constantes address */
/* r3 working area W address */
/* r5 address constantes K */
/* r6 counter t */
/* r7 block counter */
/* r8 addresse variables a b c d e f g h */
@ldr r0,iAdrtbW
@vidmemtit verifW80 r0 20
@ init variable a b c d e f g h
ldr r0,iAdrtbH
ldr r8,iAdrtbabcdefgh
mov r1,#0
loopInita:
ldr r9,[r0,r1,lsl #2]
str r9,[r8,r1,lsl #2]
add r1,r1,#1
cmp r1,#8
blt loopInita
ldr r1,iAdrtbConstHi
ldr r5,iAdrtbConstKt
mov r6,#0
loop64T: @ begin loop 64 t
ldr r9,[r8,#var_h]
ldr r10,[r8,#var_e] @ calcul T1
ror r11,r10,#6 @ fonction sigma 1
ror r12,r10,#11
eor r11,r12
ror r12,r10,#25
eor r11,r12
add r9,r9,r11 @ h + sigma1 (e)
ldr r0,[r8,#var_f] @ fonction ch x and y xor (non x and z)
ldr r4,[r8,#var_g]
and r11,r10,r0
mvn r12,r10
and r12,r12,r4
eor r11,r12
add r9,r9,r11 @ h + sigma1 (e) + ch (e,f,g)
ldr r0,[r5,r6,lsl #2] @ load constantes k0
add r9,r9,r0
ldr r0,[r3,r6,lsl #2] @ Wt
add r9,r9,r0
@ calcul T2
ldr r10,[r8,#var_a] @ fonction sigma 0
ror r11,r10,#2
ror r12,r10,#13
eor r11,r11,r12
ror r12,r10,#22
eor r11,r11,r12
ldr r2,[r8,#var_b]
ldr r4,[r8,#var_c]
@ fonction maj x and y xor x and z xor y and z
and r12,r10,r2
and r0,r10,r4
eor r12,r12,r0
and r0,r2,r4
eor r12,r12,r0 @
add r12,r12,r11 @ T2
@ compute variables
ldr r4,[r8,#var_g]
str r4,[r8,#var_h]
ldr r4,[r8,#var_f]
str r4,[r8,#var_g]
ldr r4,[r8,#var_e]
str r4,[r8,#var_f]
ldr r4,[r8,#var_d]
add r4,r4,r9 @ add T1
str r4,[r8,#var_e]
ldr r4,[r8,#var_c]
str r4,[r8,#var_d]
ldr r4,[r8,#var_b]
str r4,[r8,#var_c]
ldr r4,[r8,#var_a]
str r4,[r8,#var_b]
add r4,r9,r12 @ add T1 T2
str r4,[r8,#var_a]
mov r0,r8
add r6,r6,#1 @ increment t
cmp r6,#64
blt loop64T
@ End block
ldr r0,iAdrtbH @ start area H
mov r10,#0
loopStoreH:
ldr r9,[r8,r10,lsl #2]
ldr r3,[r0,r10,lsl #2]
add r3,r9
str r3,[r0,r10,lsl #2] @ store variables in H0
add r10,r10,#1
cmp r10,#8
blt loopStoreH
@ other bloc
add r7,#1 @ increment block
ldr r0,iAdriNbBlocs
ldr r4,[r0] @ restaur maxi block
cmp r7,r4 @ maxi ?
blt loopBlock @ loop other block
ldr r0,iAdrtbH @ return result area H
100:
pop {r1-r12,lr} @ restaur registers
bx lr @ return
iAdrtbConstHi: .int tbConstHi
iAdrtbConstKt: .int tbConstKt
iAdrtbH: .int tbH
iAdrtbW: .int tbW
iAdrtbabcdefgh: .int tbabcdefgh
iAdriNbBlocs: .int iNbBlocs
iAdrsZoneTrav: .int sZoneTrav
/******************************************************************/
/* inversion des mots de 32 bits d un bloc */
/******************************************************************/
/* r0 contains N° block */
inversion:
push {r1-r3,lr} @ save registers
ldr r1,iAdrsZoneTrav
add r1,r0,lsl #6 @ debut du bloc
mov r2,#0
1: @ start loop
ldr r3,[r1,r2,lsl #2]
rev r3,r3
str r3,[r1,r2,lsl #2]
add r2,r2,#1
cmp r2,#16
blt 1b
100:
pop {r1-r3,lr} @ restaur registres
bx lr @return
/******************************************************************/
/* display hash SHA256 */
/******************************************************************/
/* r0 contains the address of hash */
displaySHA256:
push {r1-r3,lr} @ save registres
mov r3,r0
mov r2,#0
1:
ldr r0,[r3,r2,lsl #2] @ load 4 bytes
@rev r0,r0 @ reverse bytes
ldr r1,iAdrsZoneConv
bl conversion16 @ conversion hexa
mov r4,#0
strb r4,[r1,r0] @ 0 final
ldr r0,iAdrsZoneConv
bl affichageMess
add r2,r2,#1
cmp r2,#LGHASH / 4
blt 1b @ and loop
ldr r0,iAdrszCarriageReturn
bl affichageMess @ display message
100:
pop {r1-r3,lr} @ restaur registers
bx lr @ return
iAdrsZoneConv: .int sZoneConv
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
Start hash number : 22
A4F902CF9D51FE51EDA156A6792E1445DFF65EDF3A217A1F3334CC9CF1495C2C
</pre>
=={{header|C}}==
{{libheader|GLib}}
<syntaxhighlight lang="c">#include <glib.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
guchar* sha256_merkle_tree(FILE* in, size_t block_size) {
gchar* buffer = g_malloc(block_size);
GPtrArray* hashes = g_ptr_array_new_with_free_func(g_free);
gssize digest_length = g_checksum_type_get_length(G_CHECKSUM_SHA256);
GChecksum* checksum = g_checksum_new(G_CHECKSUM_SHA256);
size_t bytes;
while ((bytes = fread(buffer, 1, block_size, in)) > 0) {
g_checksum_reset(checksum);
g_checksum_update(checksum, (guchar*)buffer, bytes);
gsize len = digest_length;
guchar* digest = g_malloc(len);
g_checksum_get_digest(checksum, digest, &len);
g_ptr_array_add(hashes, digest);
}
g_free(buffer);
guint hashes_length = hashes->len;
if (hashes_length == 0) {
g_ptr_array_free(hashes, TRUE);
g_checksum_free(checksum);
return NULL;
}
while (hashes_length > 1) {
guint j = 0;
for (guint i = 0; i < hashes_length; i += 2, ++j) {
guchar* digest1 = g_ptr_array_index(hashes, i);
guchar* digest_out = g_ptr_array_index(hashes, j);
if (i + 1 < hashes_length) {
guchar* digest2 = g_ptr_array_index(hashes, i + 1);
g_checksum_reset(checksum);
g_checksum_update(checksum, digest1, digest_length);
g_checksum_update(checksum, digest2, digest_length);
gsize len = digest_length;
g_checksum_get_digest(checksum, digest_out, &len);
} else {
memcpy(digest_out, digest1, digest_length);
}
}
hashes_length = j;
}
guchar* result = g_ptr_array_steal_index(hashes, 0);
g_ptr_array_free(hashes, TRUE);
g_checksum_free(checksum);
return result;
}
int main(int argc, char** argv) {
if (argc != 2) {
fprintf(stderr, "usage: %s filename\n", argv[0]);
return EXIT_FAILURE;
}
FILE* in = fopen(argv[1], "rb");
if (in) {
guchar* digest = sha256_merkle_tree(in, 1024);
fclose(in);
if (digest) {
gssize length = g_checksum_type_get_length(G_CHECKSUM_SHA256);
for (gssize i = 0; i < length; ++i)
printf("%02x", digest[i]);
printf("\n");
g_free(digest);
}
} else {
perror(argv[1]);
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|C++}}==
{{libheader|OpenSSL}}
<syntaxhighlight lang="cpp">#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <vector>
#include <openssl/sha.h>
class sha256_exception : public std::exception {
public:
const char* what() const noexcept override {
return "SHA-256 error";
}
};
class sha256 {
public:
sha256() { reset(); }
sha256(const sha256&) = delete;
sha256& operator=(const sha256&) = delete;
void reset() {
if (SHA256_Init(&context_) == 0)
throw sha256_exception();
}
void update(const void* data, size_t length) {
if (SHA256_Update(&context_, data, length) == 0)
throw sha256_exception();
}
std::vector<unsigned char> digest() {
std::vector<unsigned char> digest(SHA256_DIGEST_LENGTH);
if (SHA256_Final(digest.data(), &context_) == 0)
throw sha256_exception();
return digest;
}
private:
SHA256_CTX context_;
};
std::string digest_to_string(const std::vector<unsigned char>& digest) {
std::ostringstream out;
out << std::hex << std::setfill('0');
for (size_t i = 0; i < digest.size(); ++i)
out << std::setw(2) << static_cast<int>(digest[i]);
return out.str();
}
std::vector<unsigned char> sha256_merkle_tree(std::istream& in, size_t block_size) {
std::vector<std::vector<unsigned char>> hashes;
std::vector<char> buffer(block_size);
sha256 md;
while (in) {
in.read(buffer.data(), block_size);
size_t bytes = in.gcount();
if (bytes == 0)
break;
md.reset();
md.update(buffer.data(), bytes);
hashes.push_back(md.digest());
}
if (hashes.empty())
return {};
size_t length = hashes.size();
while (length > 1) {
size_t j = 0;
for (size_t i = 0; i < length; i += 2, ++j) {
auto& digest1 = hashes[i];
auto& digest_out = hashes[j];
if (i + 1 < length) {
auto& digest2 = hashes[i + 1];
md.reset();
md.update(digest1.data(), digest1.size());
md.update(digest2.data(), digest2.size());
digest_out = md.digest();
} else {
digest_out = digest1;
}
}
length = j;
}
return hashes[0];
}
int main(int argc, char** argv) {
if (argc != 2) {
std::cerr << "usage: " << argv[0] << " filename\n";
return EXIT_FAILURE;
}
std::ifstream in(argv[1], std::ios::binary);
if (!in) {
std::cerr << "Cannot open file " << argv[1] << ".\n";
return EXIT_FAILURE;
}
try {
std::cout << digest_to_string(sha256_merkle_tree(in, 1024)) << '\n';
} catch (const std::exception& ex) {
std::cerr << ex.what() << "\n";
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.Classes}}
{{libheader| DCPsha256}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program SHA256_Merkle_tree;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
System.Classes,
DCPsha256;
function SHA256(const Input: TArray<Byte>; Len: Integer = -1): TArray<Byte>;
var
Hasher: TDCP_sha256;
l: Integer;
begin
if Len < 0 then
l := length(Input)
else
l := Len;
Hasher := TDCP_sha256.Create(nil);
try
Hasher.Init;
Hasher.Update(Input[0], l);
SetLength(Result, Hasher.HashSize div 8);
Hasher.final(Result[0]);
finally
Hasher.Free;
end;
end;
function Merkle_tree(FileName: TFileName): string;
const
blockSize = 1024;
var
f: TMemoryStream;
hashes: TArray<TArray<byte>>;
bytesRead: Cardinal;
buffer: TArray<byte>;
i, index: Integer;
begin
Result := '';
if not FileExists(FileName) then
exit;
SetLength(buffer, blockSize);
FillChar(buffer[0], blockSize, 0);
f := TMemoryStream.Create;
f.LoadFromFile(FileName);
index := 0;
repeat
bytesRead := f.Read(buffer, blockSize);
if 0 = bytesRead then
Break;
Insert(SHA256(buffer, bytesRead), hashes, index);
inc(index);
until false;
f.Free;
SetLength(buffer, 64);
while Length(hashes) > 1 do
begin
var hashes2: TArray<TArray<byte>>;
index := 0;
i := 0;
while i < length(hashes) do
begin
if i < length(hashes) - 1 then
begin
buffer := copy(hashes[i], 0, length(hashes[i]));
buffer := concat(buffer, copy(hashes[i + 1], 0, length(hashes[i])));
Insert(SHA256(buffer), hashes2, index);
inc(index);
end
else
begin
Insert(hashes[i], hashes2, index);
inc(index);
end;
inc(i, 2);
end;
hashes := hashes2;
end;
Result := '';
for var b in hashes[0] do
begin
Result := Result + b.ToHexString(2);
end;
end;
begin
writeln(Merkle_tree('title.png'));
readln;
end.</syntaxhighlight>
{{out}}
<pre>A4F902CF9D51FE51EDA156A6792E1445DFF65EDF3A217A1F3334CC9CF1495C2C</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 2020-08-14}}
<syntaxhighlight lang="factor">USING: checksums checksums.sha fry grouping io
io.encodings.binary io.files kernel make math math.parser
namespaces sequences ;
: each-block ( ... size quot: ( ... block -- ... ) -- ... )
input-stream get spin (each-stream-block) ; inline
: >sha-256 ( seq -- newseq ) sha-256 checksum-bytes ;
: (hash-read) ( path encoding chunk-size -- )
'[ _ [ >sha-256 , ] each-block ] with-file-reader ;
! Read a file in chunks as a sequence of sha-256 hashes, so as
! not to store a potentially large file in memory all at once.
: hash-read ( path chunk-size -- seq )
binary swap [ (hash-read) ] { } make ;
: hash-combine ( seq -- newseq )
2 <groups>
[ dup length 1 > [ concat >sha-256 ] [ first ] if ] map ;
: merkle-hash ( path chunk-size -- str )
hash-read [ dup length 1 = ] [ hash-combine ] until first
bytes>hex-string ;
"title.png" 1024 merkle-hash print</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Go}}==
<
import (
Line 58 ⟶ 1,696:
fmt.Printf("%x", hashes[0])
fmt.Println()
}</
{{out}}
Line 65 ⟶ 1,703:
</pre>
=={{header|
<syntaxhighlight lang="haskell">{-# LANGUAGE BangPatterns, LambdaCase #-}
import Control.Monad (mfilter)
import Crypto.Hash.SHA256 (hash)
import qualified Data.ByteString as B
import Data.ByteString.Builder (byteStringHex, char7, hPutBuilder)
import Data.Functor ((<&>))
import Data.Maybe (listToMaybe)
import Data.Strict.Tuple (Pair(..))
import qualified Data.Strict.Tuple as T
import System.Environment (getArgs)
import System.IO (Handle, stdin, stdout)
import System.IO.Streams (InputStream)
import qualified System.IO.Streams as S
import Text.Read (readMaybe)
type Node a = Pair Int a
type LevelPred = Int -> Int -> Bool
type Combine a = a -> a -> a
-- From a stream of nodes construct the root of a tree from the bottom up. For
-- each level of the tree pairs of nodes are combined to form a parent node one
-- level higher. Use a stack to store nodes waiting to be combined with another
-- node on their level. (An exception to this is at the end of processing,
-- where all the nodes on the stack can be combined.)
build :: Combine a -> [Node a] -> InputStream (Node a) -> IO (Maybe (Node a))
build combine !stack is = S.read is >>= \case
Nothing -> return $ listToMaybe $ reduce always combine stack
Just h -> build combine (reduce (==) combine (h:stack)) is
-- Given a predicate, combining function and a stack, then as long as the
-- predicate is true, repeatedly replace the two top values on the stack with
-- their combined values.
reduce :: LevelPred -> Combine a -> [Node a] -> [Node a]
reduce prd combine (x@(i :!: _):y@(j :!: _):zs)
| prd i j = reduce prd combine (nodeLift combine y x : zs)
reduce _ _ zs = zs
-- Apply a combining function to the values in two nodes while calculating the
-- appropriate level for the new node.
nodeLift :: Combine a -> Node a -> Node a -> Node a
nodeLift f (i :!: x) (j :!: y) = max i j + 1 :!: f x y
always :: a -> b -> Bool
always _ _ = True
-- Build a SHA256-based Merkle tree using bytes read from a handle, and hashing
-- the data using the given chunk size.
merkleTreeSha256 :: Int -> Handle -> IO (Maybe B.ByteString)
merkleTreeSha256 sz h = mkHash <&> fmap T.snd
where mkHash = S.makeInputStream getBuf >>=
S.map (\bs -> 0 :!: hash bs) >>=
build (\x y -> hash (x `B.append` y)) []
getBuf = B.hGet h sz <&> (mfilter (/= B.empty) . Just)
-- Print a ByteString in hex.
printByteStringHex :: B.ByteString -> IO ()
printByteStringHex = hPutBuilder stdout . (<> char7 '\n') . byteStringHex
main :: IO ()
main = getArgs <&> map readMaybe >>= \case
[Just sz] -> merkleTreeSha256 sz stdin >>= \case
Nothing -> putStrLn "No input to hash"
Just h -> printByteStringHex h
_ -> putStrLn "Argument usage: chunk-size"</syntaxhighlight>
{{out}}
<pre>
Line 114 ⟶ 1,775:
</pre>
=={{header|
<syntaxhighlight lang="java">import java.io.*;
import java.security.*;
import java.util.*;
public class SHA256MerkleTree {
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("missing file argument");
System.exit(1);
}
try (InputStream in = new BufferedInputStream(new FileInputStream(args[0]))) {
byte[] digest = sha256MerkleTree(in, 1024);
if (digest != null)
System.out.println(digestToString(digest));
} catch (Exception e) {
e.printStackTrace();
}
}
private static String digestToString(byte[] digest) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < digest.length; ++i)
result.append(String.format("%02x", digest[i]));
return result.toString();
private static byte[] sha256MerkleTree(InputStream in, int blockSize) throws Exception {
byte[] buffer = new byte[blockSize];
int bytes;
MessageDigest md = MessageDigest.getInstance("SHA-256");
List<byte[]> digests = new ArrayList<>();
while ((bytes = in.read(buffer)) > 0) {
md.reset();
md.update(buffer, 0, bytes);
digests.add(md.digest());
}
int length = digests.size();
if (length == 0)
return null;
while (length > 1) {
int j = 0;
for (int i = 0; i < length; i += 2, ++j) {
byte[] digest1 = digests.get(i);
if (i + 1 < length) {
byte[] digest2 = digests.get(i + 1);
md.reset();
md.update(digest1);
md.update(digest2);
digests.set(j, md.digest());
} else {
digests.set(j, digest1);
}
}
length = j;
}
return digests.get(0);
}
}</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using SHA
function merkletree(filename="title.png", blocksize=1024)
bytes = codeunits(read(filename, String))
len = length(bytes)
hsh = [sha256(view(bytes. i:min(i+blocksize-1, len)])) for i in 1:1024:len]
len = length(hsh)
while len > 1
hsh = [i == len ? hsh[i] : sha256(vcat(hsh[i], hsh[i + 1])) for i in 1:2:len]
len = length(hsh)
end
return bytes2hex(hsh[1])
end
println(merkletree())
</syntaxhighlight>{{out}}
<pre>a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">data=Import["https://rosettacode.org/mw/title.png","Byte"];
parts=Hash[ByteArray[#],"SHA256","ByteArray"]&/@Partition[data,UpTo[1024]];
parts=NestWhile[If[Length[#]==2,Hash[Join@@#,"SHA256","ByteArray"],First[#]]&/@Partition[#,UpTo[2]]&,parts,Length[#]>1&];
StringJoin[IntegerString[Normal[First[parts]],16]]</syntaxhighlight>
{{out}}
<pre>a4f92cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c</pre>
=={{header|Nim}}==
{{libheader|nimcrypto}}
To compute the digests of file blocks, we use the procedure “digest” which accepts the address of a byte array and a byte count. To compute the digests of pairs of digests, we use instead a SHA256 context and the procedures “update” and “finish”, which avoids a copy in an intermediate buffer.
<syntaxhighlight lang="nim">
import nimcrypto
const BlockSize = 1024
var hashes: seq[MDigest[256]]
let f = open("title.png")
var buffer: array[BlockSize, byte]
while true:
let n = f.readBytes(buffer, 0, BlockSize)
if n == 0: break
hashes.add sha256.digest(buffer[0].addr, n.uint)
f.close()
var ctx: sha256
while hashes.len != 1:
var newHashes: seq[MDigest[256]]
for i in countup(0, hashes.high, 2):
if i < hashes.high:
ctx.init()
ctx.update(hashes[i].data)
ctx.update(hashes[i + 1].data)
newHashes.add ctx.finish()
ctx.clear()
else:
newHashes.add hashes[i]
hashes= newHashes
echo hashes[0]</syntaxhighlight>
{{out}}
<pre>A4F902CF9D51FE51EDA156A6792E1445DFF65EDF3A217A1F3334CC9CF1495C2C</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
minimal modified [http://rosettacode.org/wiki/SHA-256_Merkle_tree#Delphi Delphi] version
<syntaxhighlight lang="pascal">
program SHA256_Merkle_tree;
{$IFDEF WINDOWS}
{$APPTYPE CONSOLE}
{$ENDIF}
{$IFDEF DELPHI}
uses
System.SysUtils,
System.Classes,
DCPsha256;
type
TmyByte = TArray<Byte>;
TmyHashes = TArray<TArray<byte>>;
{$ENDIF}
{$IFDEF FPC}
{$Mode DELPHI}
uses
SysUtils,
Classes,
DCPsha256;
type
TmyByte = array of byte;
TmyHashes = array of TmyByte;
{$ENDIF}
function SHA256(const Input: TmyByte; Len: Integer = -1): TmyByte;
var
Hasher: TDCP_sha256;
l: Integer;
begin
if Len < 0 then
l := length(Input)
else
l := Len;
Hasher := TDCP_sha256.Create(nil);
try
Hasher.Init;
Hasher.Update(Input[0], l);
SetLength(Result, Hasher.HashSize div 8);
Hasher.final(Result[0]);
finally
Hasher.Free;
end;
end;
function Merkle_tree(FileName: TFileName): string;
const
blockSize = 1024;
var
f: TMemoryStream;
hashes,
hashes2: TmyHashes;
bytesRead: Cardinal;
buffer: TmyByte;
i, index: Integer;
b: byte;
begin
Result := '';
if not FileExists(FileName) then
exit;
SetLength(buffer, blockSize);
FillChar(buffer[0], blockSize, #0);
f := TMemoryStream.Create;
f.LoadFromFile(FileName);
index := 0;
repeat
//freepascal needs buffer[0] instead buffer
bytesRead := f.Read(buffer[0], blockSize);
if bytesRead= 0 then
BREAK;
Insert(SHA256(buffer, bytesRead), hashes, index);
inc(index);
until bytesRead<blockSize;
f.Free;
SetLength(buffer, 64);
while Length(hashes) > 1 do
begin
//first clear old hashes2
setlength(hashes2,0);
index := 0;
i := 0;
while i < length(hashes) do
begin
if i < length(hashes) - 1 then
begin
buffer := copy(hashes[i], 0, length(hashes[i]));
buffer := concat(buffer,copy(hashes[i + 1], 0, length(hashes[i])));
Insert(SHA256(buffer), hashes2, index);
inc(index);
end
else
begin
Insert(hashes[i], hashes2, index);
inc(index);
end;
inc(i, 2);
end;
hashes := hashes2;
end;
Result := '';
for b in hashes[0] do
begin
Result := Result + b.ToHexString(2);
end;
end;
begin
writeln(Merkle_tree('title.png'));
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.</syntaxhighlight>
{{out}}
<pre>
A4F902CF9D51FE51EDA156A6792E1445DFF65EDF3A217A1F3334CC9CF1495C2C
</pre>
=={{header|Perl}}==
{{Trans|Raku}}
<syntaxhighlight lang="perl"># 20210222 Perl programming solution
use strict;
use warnings;
use Crypt::Digest::SHA256 'sha256' ;
my @blocks;
open my $fh, '<:raw', './title.png';
while ( read $fh, my $chunk, 1024 ) { push @blocks, sha256 $chunk }
while ( scalar @blocks > 1 ) {
my @clone = @blocks and @blocks = ();
while ( @_ = splice @clone, 0, 2 ) {
push @blocks, scalar @_ == 1 ? $_[0] : sha256 $_[0].$_[1]
}
}
print unpack ( 'H*', $blocks[0] ) , "\n";</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Phix}}==
{{libheader|Phix/libcurl}}
<!--<syntaxhighlight lang="phix">(notonline)-->
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #000000;">libcurl</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #000000;">sha256</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">ONE_MB</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1024</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">1024</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">merkle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">filename</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">url</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">block_size</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ONE_MB</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">file_exists</span><span style="color: #0000FF;">(</span><span style="color: #000000;">filename</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Downloading %s...\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">filename</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">CURLcode</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">curl_easy_get_file</span><span style="color: #0000FF;">(</span><span style="color: #000000;">url</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">filename</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (no proxy)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">CURLE_OK</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #000000;">CURLE_COULDNT_RESOLVE_HOST</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">error</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">" [CURLE_COULDNT_RESOLVE_HOST]"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"Error %s downloading file\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">error</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_text</span><span style="color: #0000FF;">(</span><span style="color: #000000;">filename</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">block_size</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">blocks</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sha256</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">block_size</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">))]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">sha256</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #0000FF;">:</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">blocks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">asHex</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%02X"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">asHex</span><span style="color: #0000FF;">(</span><span style="color: #000000;">merkle</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"title.png"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"https://rosettacode.org/mw/title.png"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1024</span><span style="color: #0000FF;">)))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Python}}==
This version attempts to combine blocks as soon as possible to minimize the memory footprint.
<syntaxhighlight lang="python">#!/usr/bin/env python
# compute the root label for a SHA256 Merkle tree built on blocks of a given
# size (default 1MB) taken from the given file(s)
import argh
import hashlib
import sys
@argh.arg('filename', nargs='?', default=None)
def main(filename, block_size=1024*1024):
if filename:
fin = open(filename, 'rb')
else:
fin = sys.stdin
stack = []
block = fin.read(block_size)
while block:
# a node is a pair: ( tree-level, hash )
node = (0, hashlib.sha256(block).digest())
stack.append(node)
# concatenate adjacent pairs at the same level
while len(stack) >= 2 and stack[-2][0] == stack[-1][0]:
a = stack[-2]
b = stack[-1]
l = a[0]
stack[-2:] = [(l+1, hashlib.sha256(a[1] + b[1]).digest())]
block = fin.read(block_size)
while len(stack) > 1:
# at the end we have to concatenate even across levels
a = stack[-2]
b = stack[-1]
al = a[0]
bl = b[0]
stack[-2:] = [(max(al, bl)+1, hashlib.sha256(a[1] + b[1]).digest())]
print(stack[0][1].hex())
argh.dispatch_command(main)
</syntaxhighlight>
{{Out}}
<pre>$ sha256tree.py -
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>use Digest::SHA256::Native;
unit sub
my $in = @args ?? IO::CatHandle.new(@args) !! $*IN;
my @blocks = do while my $block = $in.read: $block-size { sha256 $block };
while @blocks > 1
@blocks = @blocks.batch(2).map: { $_ > 1 ?? sha256([~] $_) !! .[0] }
say @blocks[0]».fmt('%02x').join;</syntaxhighlight>
{{Out}}
<pre>$ sha256tree --block-size=1024 title.png
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">extern crate crypto;
use crypto::digest::Digest;
use crypto::sha2::Sha256;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
fn sha256_merkle_tree(filename: &str, block_size: usize) -> std::io::Result<Option<Vec<u8>>> {
let mut md = Sha256::new();
let mut input = BufReader::new(File::open(filename)?);
let mut buffer = vec![0; block_size];
let mut digest = vec![0; md.output_bytes()];
let mut digests = Vec::new();
loop {
let bytes = input.read(&mut buffer)?;
if bytes == 0 {
break;
}
md.reset();
md.input(&buffer[0..bytes]);
md.result(&mut digest);
digests.push(digest.clone());
}
let mut len = digests.len();
if len == 0 {
return Ok(None);
}
while len > 1 {
let mut j = 0;
let mut i = 0;
while i < len {
if i + 1 < len {
md.reset();
md.input(&digests[i]);
md.input(&digests[i + 1]);
md.result(&mut digests[j]);
} else {
digests.swap(i, j);
}
i += 2;
j += 1;
}
len = j;
}
Ok(Some(digests[0].clone()))
}
fn digest_to_string(digest: &[u8]) -> String {
let mut result = String::new();
for x in digest {
result.push_str(&format!("{:02x}", x));
}
result
}
fn main() {
match sha256_merkle_tree("title.png", 1024) {
Ok(Some(digest)) => println!("{}", digest_to_string(&digest)),
Ok(None) => {}
Err(error) => eprintln!("I/O error: {}", error),
}
}</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
=={{header|Wren}}==
{{libheader|Wren-crypto}}
{{libheader|Wren-seq}}
{{libheader|Wren-str}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "io" for File
import "./crypto" for Sha256, Bytes
import "./seq" for Lst
import "./str" for Str
import "./fmt" for Conv
var bytes = File.read("title.png").bytes.toList
var chunks = Lst.chunks(bytes, 1024)
var hashes = List.filled(chunks.count, null)
var i = 0
for (chunk in chunks) {
var h = Sha256.digest(chunk.map { |b| String.fromByte(b) }.join())
hashes[i] = Str.chunks(h, 2).map { |x| Conv.atoi(x, 16) }.toList
i = i + 1
}
var buffer = List.filled(64, 0)
while (hashes.count > 1) {
var hashes2 = []
var i = 0
while (i < hashes.count) {
if (i < hashes.count - 1) {
for (j in 0..31) buffer[j] = hashes[i][j]
for (j in 0..31) buffer[j+32] = hashes[i+1][j]
var h = Sha256.digest(buffer.map { |b| String.fromByte(b) }.join())
var hb = Str.chunks(h, 2).map { |x| Conv.atoi(x, 16) }.toList
hashes2.add(hb)
} else {
hashes2.add(hashes[i])
}
i = i + 2
}
hashes = hashes2
}
System.print(Bytes.toHexString(hashes[0]))</syntaxhighlight>
{{out}}
<pre>
a4f902cf9d51fe51eda156a6792e1445dff65edf3a217a1f3334cc9cf1495c2c
</pre>
| |||