Support SHA256 precompile

[eigmax]

SHA256 starky reference: https://github.com/succinctlabs/starkyx/blob/1644af58bfc7d305c0066597c303a129fec7f427/starkyx/src/machine/hash/sha/sha256/register.rs

[VanhGer]

Because there are 2 phases in the Sha256: extend and compress, we need to create 2 tables for each: ShaExtend and ShaCompress
Then, because the input & output of them are different, we create 2 tables for each: ShaExtendSponge, ShaCompressSponge.

Here is the definition:

ShaExtendCols:

number of rounds: 48
input: w[i-15], w[i-2], w[i-7], w[i-16].
Columns:

• timestamp:
• i:
• w_i_minus_1: from input
• w_i_minus_2: from input
• w_i_minus_16: from input
• w_i_minus_7: from input
• s_0: compute from w_i_minus_15
• s_1: compute from w_i_minus_2
• w_i: compute from s_0, s_1, w_i_minus_16, w_i_minus_7 /// output

i	w_i_minus_1	w_i_minus_2	w_i_minus_16	w_i_minus_7	s_0	s_1	w_i

constraints:

• s_0 = w_i_minus_15.rotate_right(7) ^ w_i_minus_15.rotate_right(18) ^ (w_i_minus_15 >> 3)
• s_1 = w_i_minus_2.rotate_right(17) ^ w_i_minus_2.rotate_right(19) ^ (w_i_minus_2 >> 10);
• w_i = s1 + w_i_minus_16 + s0 + w_i_minus_7;

ShaExtendSpongeCols: handle the input/output of ShaExtend

for each block:

..		i	w_i_minus_1	w_i_minus_2	w_i_minus_16	w_i_minus_7	w_i

constraints:

• check the w_i_minus_1 | w_i_minus_2 | w_i_minus_16 | w_i_minus_7 are read correctly from memory?

ShaCompressCols:

input: a,b,c,.., h, SHA_COMPRESS_K[i]
number of rounds: 64

• timestamp
• i
• w[i]: read from memory
• a, b, ..., h
• s1: compute from e
• ch: compute from e, f, g
• T_1: compute from h, s1, ch, SHA_COMPRESS_K[i], w[i]
• s0: compute from a
• maj: compute from a, b, c
• T_2: compute from s0, maj
  output: [u32; 8] : [g, f, e, d+T_1, c, b, a, T_1 + T_2].reverse()

i	w_i	a, b,...,h	SHA_COMPRESS_K[i]	s1	ch	T_1	s_0	maj	t_2	output

constraints:

• s1 = e.rotate_right(6) ^ e.rotate_right(11) ^ e.rotate_right(25)
• ch = (e & f) ^ (!e & g)
• temp1 = h + s1 + ch + SHA_COMPRESS_K[i] + w_i;
• s0 = a.rotate_right(2) ^ a.rotate_right(13) ^ a.rotate_right(22);
• maj = (a & b) ^ (a & c) ^ (b & c);
• temp2 = s0 + maj

ShaCompressSponge

first_block	i	w_i	SHA_COMPRESS_K[i]	a, b...h	output
				a, b,...h

constraints:

• we need to check: output of local = a,b,...h of next.
• w_i, SHA_COMPRESS_K[i] are read correctly from memory
• the value of a,b,...,h when first_block is on should equal to: [
  0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19, ]However, there is still a final step:

    // Execute the "finalize" phase.
    let v = [a, b, c, d, e, f, g, h];
    let mut cpu_row = CpuColumnsView::default();
    cpu_row.clock = F::from_canonical_usize(state.traces.clock());
    for i in 0..8 {
        let addr = MemoryAddress::new(0, Segment::Code, h_ptr + i * 4);
        let mem_op =
            mem_write_gp_log_and_fill(i, addr, state, &mut cpu_row, hx[i].wrapping_add(v[i]));
        state.traces.push_memory(mem_op);
    }

I do not know how to handle this.
And also the lookup table for 4 tables about. Maybe we need one more table.