nx_jpeg_zigzag.nx source

1// nx_jpeg_zigzag.nx -- inverse zig-zag scan order for JPEG 8x8 blocks. 2// Per ITU-T Rec. T.81 Fig. A.6 / table H.1. 3// 4// JPEG stores DCT coefficients in zig-zag order to cluster non-zero 5// coefficients near the start of the stream (improves run-length 6// coding efficiency). Decoding pipeline needs the inverse: 7// 8// natural_block[un_zigzag[k]] = zigzag_block[k] 9// 10// for k in 0..63. This file ships the 64-entry inverse-zigzag table 11// AND a primitive that applies it to an 8x8 i64 coefficient block. 12// 13// The zig-zag scan visits 8x8 block positions in this order 14// (T.81 Fig. A.6): 15// 16// 0 1 5 6 14 15 27 28 17// 2 4 7 13 16 26 29 42 18// 3 8 12 17 25 30 41 43 19// 9 11 18 24 31 40 44 53 20// 10 19 23 32 39 45 52 54 21// 20 22 33 38 46 51 55 60 22// 21 34 37 47 50 56 59 61 23// 35 36 48 49 57 58 62 63 24// 25// nx_safety_envelope: 26// intended_use: "8x8 DCT-block un-zigzag for JPEG decode." 27// sil_target: SIL1 28// evidence: [t81_figure_a6_canonical_basis, 29// fixed_64_entry_table_bit_exact_reproducible] 30// verdict: NOT_YET_EVALUATED 31 32import "nx_syscalls.nx" 33 34// Initialise a caller-supplied 64-entry i64 buffer with the inverse 35// zigzag table: un_zigzag[k] = natural-order position of the k-th 36// zigzag-order coefficient. 37func nx_jpeg_zigzag_inverse_table(out: *i64) -> i64 { 38 out[ 0]= 0; out[ 1]= 1; out[ 2]= 8; out[ 3]=16; out[ 4]= 9; out[ 5]= 2; out[ 6]= 3; out[ 7]=10 39 out[ 8]=17; out[ 9]=24; out[10]=32; out[11]=25; out[12]=18; out[13]=11; out[14]= 4; out[15]= 5 40 out[16]=12; out[17]=19; out[18]=26; out[19]=33; out[20]=40; out[21]=48; out[22]=41; out[23]=34 41 out[24]=27; out[25]=20; out[26]=13; out[27]= 6; out[28]= 7; out[29]=14; out[30]=21; out[31]=28 42 out[32]=35; out[33]=42; out[34]=49; out[35]=56; out[36]=57; out[37]=50; out[38]=43; out[39]=36 43 out[40]=29; out[41]=22; out[42]=15; out[43]=23; out[44]=30; out[45]=37; out[46]=44; out[47]=51 44 out[48]=58; out[49]=59; out[50]=52; out[51]=45; out[52]=38; out[53]=31; out[54]=39; out[55]=46 45 out[56]=53; out[57]=60; out[58]=61; out[59]=54; out[60]=47; out[61]=55; out[62]=62; out[63]=63 46 return 0 47} 48 49// Apply inverse zig-zag to a 64-entry coefficient array. 50// src[k] = zigzag-order coefficient k 51// dst[natural_pos] = src[k] where natural_pos = un_zigzag[k] 52// `dst` must NOT alias `src` (caller responsibility). 53func nx_jpeg_un_zigzag(src: *i64, dst: *i64) -> i64 { 54 let table: *i64 = sys_mmap(64 * 8) as *i64 55 nx_jpeg_zigzag_inverse_table(table) 56 var k: i64 = 0 57 while k < 64 { 58 dst[table[k]] = src[k] 59 k = k + 1 60 } 61 return 0 62}