Sitelet https://github.com/Snezhkko/cairo/commit/28d9f3d63e7fb5b78287de319c7f96f21e4dae32
Skip to content

Commit 28d9f3d

Browse files
oriziorizi
authored
Optimized sha256 padding code. (starkware-libs#9360)
1 parent 9a6da63 commit 28d9f3d

5 files changed

Lines changed: 16040 additions & 16457 deletions

File tree

‎corelib/src/sha256.cairo‎

Lines changed: 98 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -124,99 +124,55 @@ pub fn compute_sha256_byte_array(arr: @ByteArray) -> [u32; 8] {
124124
/// * `last_input_word` - Final word for non-word-aligned inputs
125125
/// * `last_input_num_bytes` - Number of valid bytes in last_input_word
126126
fn add_sha256_padding(ref arr: Array<u32>, last_input_word: u32, last_input_num_bytes: u32) {
127-
let len = arr.len();
128-
if last_input_num_bytes == 0 {
129-
arr.append(0x80000000);
130-
} else {
131-
let (q, m, pad) = if last_input_num_bytes == 1 {
132-
(0x100, 0x1000000, 0x800000)
133-
} else if last_input_num_bytes == 2 {
134-
(0x10000, 0x10000, 0x8000)
135-
} else {
136-
(0x1000000, 0x100, 0x80)
137-
};
138-
let (_, r) = crate::integer::u32_safe_divmod(last_input_word, q);
139-
arr.append(r * m + pad);
140-
}
141-
142-
let mut remaining: felt252 = 16 - ((arr.len() + 1) % 16).into();
143-
144-
append_zeros(ref arr, remaining);
127+
let bitlen = conversions::bitlen(arr.len(), last_input_num_bytes);
128+
arr.append(conversions::to_last_word(last_input_word, last_input_num_bytes));
129+
// Now writing the length in bits, at the end of a block.
130+
// We always need to append a zero to the array, as the length is actually the two last u32
131+
// words, in which we assume the least significant is enough.
132+
let zero = 0;
133+
arr.append(zero);
134+
// Now we make sure we fill all the remaining space in the block, without the last word.
135+
let mut remaining = 15 - (arr.len() % 16).into();
136+
repeatedly_append_value(ref arr, remaining, zero);
137+
arr.append(bitlen);
138+
}
145139

146-
arr.append(len * 32 + last_input_num_bytes * 8);
140+
/// Appends `count` `value`s to the array.
141+
fn repeatedly_append_value(ref arr: Array<u32>, count: felt252, value: u32) {
142+
let mut remaining = count;
143+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 0`.
144+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 1`.
145+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 2`.
146+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 3`.
147+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 4`.
148+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 5`.
149+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 6`.
150+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 7`.
151+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 8`.
152+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 9`.
153+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 10`.
154+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 11`.
155+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 12`.
156+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 13`.
157+
dec_and_append_or_return!(remaining, arr, value); // returns if `count == 14`.
147158
}
148159

149-
/// Appends `count` zeros to the array.
150-
fn append_zeros(ref arr: Array<u32>, count: felt252) {
151-
if count == 0 {
152-
return;
153-
}
154-
arr.append(0);
155-
if count == 1 {
156-
return;
157-
}
158-
arr.append(0);
159-
if count == 2 {
160-
return;
161-
}
162-
arr.append(0);
163-
if count == 3 {
164-
return;
165-
}
166-
arr.append(0);
167-
if count == 4 {
168-
return;
169-
}
170-
arr.append(0);
171-
if count == 5 {
172-
return;
173-
}
174-
arr.append(0);
175-
if count == 6 {
176-
return;
177-
}
178-
arr.append(0);
179-
if count == 7 {
180-
return;
181-
}
182-
arr.append(0);
183-
if count == 8 {
184-
return;
185-
}
186-
arr.append(0);
187-
if count == 9 {
188-
return;
189-
}
190-
arr.append(0);
191-
if count == 10 {
192-
return;
193-
}
194-
arr.append(0);
195-
if count == 11 {
196-
return;
197-
}
198-
arr.append(0);
199-
if count == 12 {
200-
return;
201-
}
202-
arr.append(0);
203-
if count == 13 {
204-
return;
205-
}
206-
arr.append(0);
207-
if count == 14 {
208-
return;
209-
}
210-
arr.append(0);
211-
if count == 15 {
212-
return;
213-
}
214-
arr.append(0);
160+
/// Macro to decrement a counter and append a value to an array, or return if the counter is value.
161+
macro dec_and_append_or_return {
162+
($remaining: ident, $arr: ident, $value: ident) => {
163+
if $remaining == 0 {
164+
return;
165+
}
166+
$remaining -= 1;
167+
$arr.append($value);
168+
};
215169
}
216170

217171
mod conversions {
218172
#[feature("bounded-int-utils")]
219-
use core::internal::bounded_int::{self, AddHelper, BoundedInt, MulHelper, UnitInt};
173+
use core::internal::bounded_int::{
174+
self, AddHelper, BoundedInt, DivRemHelper, MulHelper, UnitInt,
175+
};
220176

221177
impl U8Shift of MulHelper<u8, UnitInt<0x100>> {
222178
type Result = BoundedInt<0, 0xFF00>;
@@ -257,4 +213,60 @@ mod conversions {
257213
) -> SAB::Add::Result {
258214
bounded_int::add::<_, _, SAB::Add>(bounded_int::mul::<_, _, SAB::Mul>(word, 0x100), byte)
259215
}
216+
217+
impl DoubleU32 of MulHelper<u32, UnitInt<2>> {
218+
type Result = BoundedInt<0, 0x1FFFFFFFE>;
219+
}
220+
221+
impl DoubleU32Inc of AddHelper<BoundedInt<0, 0x1FFFFFFFE>, UnitInt<1>> {
222+
type Result = BoundedInt<1, 0x1FFFFFFFF>;
223+
}
224+
225+
impl DoubleU32IncRightPadded of MulHelper<BoundedInt<1, 0x1FFFFFFFF>, BoundedInt<0, 0x800000>> {
226+
type Result = BoundedInt<0, 0xFFFFFFFF800000>;
227+
}
228+
229+
impl DoubleU32IncRightPaddedTrim of DivRemHelper<
230+
BoundedInt<0, 0xFFFFFFFF800000>, UnitInt<0x100000000>,
231+
> {
232+
type DivT = BoundedInt<0, 0xFFFFFF>;
233+
type RemT = BoundedInt<0, 0xFFFFFFFF>;
234+
}
235+
236+
/// Returns the last word to append to the input `u32` array given the last word input.
237+
pub fn to_last_word(word: u32, len: u32) -> u32 {
238+
let shift: BoundedInt<0, 0x800000> = match len {
239+
0 => { return 0x80000000; },
240+
1 => 0x800000,
241+
2 => 0x8000,
242+
_ => 0x80,
243+
};
244+
let doubled = bounded_int::mul::<_, _, DoubleU32>(word, 2);
245+
let incremented = bounded_int::add::<_, _, DoubleU32Inc>(doubled, 1);
246+
let result = bounded_int::mul::<_, _, DoubleU32IncRightPadded>(incremented, shift);
247+
// For backwards compatibility, we make sure to ignore high bits.
248+
let (_, r) = bounded_int::div_rem::<_, _, DoubleU32IncRightPaddedTrim>(result, 0x100000000);
249+
bounded_int::upcast(r)
250+
}
251+
252+
impl ArrBitLen of MulHelper<u32, UnitInt<32>> {
253+
type Result = BoundedInt<0, 0x1FFFFFFFE0>;
254+
}
255+
256+
impl WordBitLen of MulHelper<u32, UnitInt<8>> {
257+
type Result = BoundedInt<0, 0x7FFFFFFF8>;
258+
}
259+
260+
impl FullBitLen of AddHelper<BoundedInt<0, 0x1FFFFFFFE0>, BoundedInt<0, 0x7FFFFFFF8>> {
261+
type Result = BoundedInt<0, { 0x1FFFFFFFE0 + 0x7FFFFFFF8 }>;
262+
}
263+
264+
/// Returns the bit length of the input message, given the length of the representation u32
265+
/// array and last word bytes.
266+
pub fn bitlen(arr_len: u32, last_word_bytes: u32) -> u32 {
267+
let arr_bits = bounded_int::mul::<_, _, ArrBitLen>(arr_len, 32);
268+
let last_word_bits = bounded_int::mul::<_, _, WordBitLen>(last_word_bytes, 8);
269+
bounded_int::downcast(bounded_int::add::<_, _, FullBitLen>(arr_bits, last_word_bits))
270+
.unwrap()
271+
}
260272
}

‎crates/cairo-lang-starknet-classes/src/compiled_class_hash_test_data/contracts‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -103,10 +103,10 @@ test_compiled_class_hash
103103
libfuncs_coverage__libfuncs_coverage
104104

105105
//! > compiled_class_hash
106-
7ed6a6960d3d76c77413bb7426ed049ed7f8b70dac44a229fff88c5d67b39c3
106+
5d51b7cb81347221075fee64962b7ebf66f7ce641f3453575943e391aa7d5a7
107107

108108
//! > legacy_compiled_class_hash
109-
5d02dbee8064e03707182b9b5754e9c89f7ccd91be33133cebd95f7b58496e6
109+
56e7ea805897fa615e927033a7ee84ae057fee222e96d6d1ccac4125482673a
110110

111111
//! > ==========================================================================
112112

0 commit comments

Comments
 (0)