Lossless JPEG Decoding: JPEG-LL

This is not JPEG-LS. JPEG-LL is the lossless mode of operation defined in the original T.81 from 1992.

Note: I could not find any example JPEG-LL on the Internet to test the decoder, except the 4 images included in T.83.

Decoding is a sample-by-sample, line-by-line reconstruction. No blocks here.
Each sample is predicted from close neighbours and the difference is encoded in the data stream.
A simple and fast compression algorithm with a ratio about 2:1.

Predictor + Difference = sample value

Difference is entropy-coded (Huffman or arithmetic).



Predictor (Px):

   reconstructed samples
+-------+-------+-------+-----------------------  Beginning or RST
|       |       |       |    
|   P0 <--- Pa <--- Pa <---        
|   ^   |       |       |                                  P0: default predicted 
+---|---+-------+-------+-----------------
|   |   |       |       |                                  Px: ~ a,b,c (7 different)
|   Pb  |   Px  |   Px  |                                  Pa: ~ a
|   ^   |       |       |                                  Pb: ~ b
+---|---+-------+-------+--------------
|   |   |       |       |    
|   Pb  |   Px  |   Px  |                                  +---+---+
|   ^   |       |\  ^   |                                  | c | b |
+---|---+-------+-\-|---+-----------                       +---+---+   
|   |   |       |  \|   |                                  | a | x | 
|   Pb  |   Px <--- Px  |                                  +---+---+ 
|       |       |       |    
+-------+-------+-------+-------


Difference:

0-32768 entropy-coded value


Notes..

ITU T.83 lossless JPEG example

P2.JPEG is a 16 bit per sample LL-JPEG using arithmetic coding. 4 scans with different filtering. Output from JPEG81 decoder:

Opening ..\ITU83\P2.jpg
00000000: FFD8 SOI
00000002: FFFE COM
0000015F: FFCC DAC
  Arithmetic Conditioning
  parameters:
  DC0 L=2 U=3
  DC1 L=1 U=3
  DC2 L=0 U=2
  DC3 L=0 U=1
0000016B: FFCB SOF11 (Arithmetic Lossless sequential)
  P=16 Y=257 X=255
  Nf=4
    Ci=254 HV=1x1 Qi=0
    Ci=253 HV=1x2 Qi=0
    Ci=252 HV=3x1 Qi=0
    Ci=251 HV=1x4 Qi=0

  0
    Sample: x=85 (1:3) y=65 (1:4)
  1
    Sample: x=85 (1:3) y=129 (1:2)
  2
    Sample: x=255 (1:1) y=65 (1:4)
  3
    Sample: x=85 (1:3) y=257 (1:1)
00000181: FFDD DRI
  Ri: 170

Decoding JPEG lossless coefficients are the final samples themselves. The reference files in T.83 are:

A16.SRC        11055 bytes
B16.SRC        21930 bytes
C16.SRC        33150 bytes
D16.SRC        43690 bytes

They contain 16-bit sample values per image component, and indeed:

.. so it seems like we did it right. Worth to mention the size of the restart interval, Ri=170, set, which is 85 x 2.

Scan data:

00000187: FFDA SOS
  Ns: 1 (Single scan)
    Cs=254 Td=0 Ta=0
  Px: 1
  Se: 0
  Ah: 0
  Pt: 0
00000191: ECS
000002C1: FFD0 RST0
000002C3: ECS
000003F1: FFD1 RST1
000003F3: ECS
00000519: FFD2 RST2
0000051B: ECS
00000646: FFD3 RST3
00000648: ECS
0000077B: FFD4 RST4
0000077D: ECS
000008AC: FFD5 RST5
000008AE: ECS
000009D8: FFD6 RST6
000009DA: ECS
00000B03: FFD7 RST7
00000B05: ECS
00000C37: FFD0 RST0
00000C39: ECS
00000D6E: FFD1 RST1
00000D70: ECS
00000E9D: FFD2 RST2
00000E9F: ECS
00000FC5: FFD3 RST3
00000FC7: ECS
000010FC: FFD4 RST4
000010FE: ECS
00001226: FFD5 RST5
00001228: ECS
0000135B: FFD6 RST6
0000135D: ECS
0000148C: FFD7 RST7
0000148E: ECS
000015B8: FFD0 RST0
000015BA: ECS
000016E4: FFD1 RST1
000016E6: ECS
0000180C: FFD2 RST2
0000180E: ECS
00001939: FFD3 RST3
0000193B: ECS
00001A67: FFD4 RST4
00001A69: ECS
00001B91: FFD5 RST5
00001B93: ECS
00001CBD: FFD6 RST6
00001CBF: ECS
00001DE9: FFD7 RST7
00001DEB: ECS
00001F18: FFD0 RST0
00001F1A: ECS
00002048: FFD1 RST1
0000204A: ECS
0000217B: FFD2 RST2
0000217D: ECS
000022A8: FFD3 RST3
000022AA: ECS
000023DB: FFD4 RST4
000023DD: ECS
00002507: FFD5 RST5
00002509: ECS
00002631: FFD6 RST6
00002633: ECS
00002762: FFD7 RST7
00002764: ECS
000027F8: FFDD DRI
  Ri: 0
000027FE: FFDA SOS
  Ns: 1 (Single scan)
    Cs=253 Td=1 Ta=0
  Px: 2
  Se: 0
  Ah: 0
  Pt: 0
00002808: ECS
00006C2E: FFDA SOS
  Ns: 1 (Single scan)
    Cs=252 Td=2 Ta=0
  Px: 4
  Se: 0
  Ah: 0
  Pt: 0
00006C38: ECS
0000D39B: FFDA SOS
  Ns: 1 (Single scan)
    Cs=251 Td=3 Ta=0
  Px: 7
  Se: 0
  Ah: 0
  Pt: 0
0000D3A5: ECS
00016642: FFD9 EOI

JPEGDecode: ENUMJPGERR_OK
dd: 0
dd: 0
dd: 0
dd: 0

In the first scan, Ri is set and Restart Markers appear. Then Ri=0 disables Restart Markers for the other 3 scans.

Finally, decoder returns ENUMJPGERR_OK.

In main() we compare differences between decoded and reference values. This gives no error: all dd are zero.