camlibs/st2205/README.st2205-compression

   1 History of the reverse engineering of the st2205 compression
   2 ------------------------------------------------------------
   3
   4 After some failed attempts by me (Hans de Goede), I asked help
   5 from Bertrik Sikken with reverse engineering the st2205 compression.
   6 He went the route of disassembling the windows binaries for uploading
   7 pictures, and wrote an algorithm description of the decompression on
   8 the picframe wiki:
   9 http://picframe.spritesserver.nl/wiki/index.php/ImageEncoding
  10
  11 A copy of this page is included below.
  12
  13 I used this description to write decompression code. The first version
  14 used header files with the lookup tables as C-code arrays and these
  15 header files were made by and given to me by Bertrik. I also wrote
  16 compression code by "simply" reversing the decompression algorithm.
  17
  18 The lookup tables were a problem, as Bertrik copied them out of
  19 the windows code, and one could argue that they are copyrightable.
  20
  21 Luckily the same tables are also present in the firmware of the
  22 picture frame, and we can read them from the frame. So the
  23 libgphoto2 st2205 camlib uses this approach to avoid any copyright
  24 issues.
  25
  26 Below is a dump of:
  27 http://picframe.spritesserver.nl/wiki/index.php/ImageEncoding
  28 Made on 19 March 2010.
  29
  30 Contents
  31
  32   • 1 Compressed image format
  33       □ 1.1 Introduction
  34       □ 1.2 Image decoding
  35           ☆ 1.2.1 Image header
  36           ☆ 1.2.2 8x8 pixel block
  37               ○ 1.2.2.1 Decoding chrominance
  38               ○ 1.2.2.2 Decoding luminance
  39               ○ 1.2.2.3 Color decoding
  40           ☆ 1.2.3 Shuffling/unshuffling
  41       □ 1.3 Table overview
  42
  43 Compressed image format
  44
  45 Images written on the keychain by the Photoviewer application are stored in
  46 a compressed form. This section describes the compressed image format.
  47
  48 NOTE: code for reading images from a ST2205-based picture photoframe has
  49 been included now (march 2010) in gphoto SVN
  50
  51 Introduction
  52
  53 The photo keychain can contain several images. A simple directory-like
  54 structure starting at address 0 contains pointers to where the actual
  55 compressed images are stored.
  56
  57 Basic principles used in the encoding:
  58
  59   • 8x8 image blocks: an image has a dimension of 128x128 pixels and is
  60     subdivided into 256 blocks of 8x8 pixels each.
  61   • YUV-like encoding: each of these 8x8 pixel blocks is separated into a
  62     brightness component and two color components and independently encoded
  63     by a lossy compression algorithm.
  64   • block shuffling: the order in which the blocks are encoded is usually
  65     not simply linear top-down left-right, but is controlled by one of
  66     several "shuffling tables" that determine where each decoded block goes
  67     into the final image. By showing the decoding process in real time and
  68     using a different shuffling table for each picture, the photo key chain
  69     can create various transition effects between the previously decoded
  70     photo and the currently decoding photo.
  71
  72 Note the above (and below) 128x128 resolution and thus 256 blocks assumes a
  73 frame with a lcd a resolution of 128x128, for displays with a different
  74 reslution this numbers change accordingly.
  75
  76 Image decoding
  77
  78 An image is encoded as a 16-byte image header, followed by the 256 blocks
  79 encoding each for an area of 8x8 pixels. Typically, each 8x8 block is
  80 encoded using 48 bytes (or in some special cases 56 or 64 bytes, see
  81 below), this means a total size of 12304 bytes. Uncompressed, the image
  82 would require 32768 bytes (assuming 16-bit RGB565 format), saving space by
  83 a factor of about 2.66.
  84
  85 Image header
  86
  87 An image starts with a 16-byte header:
  88
  89 ┌─────────┬───────────────────────────────────────────────────────────────┐
  90 │  Byte   │                            Meaning                            │
  91 ├─────────┼───────────────────────────────────────────────────────────────┤
  92 │0x00     │Image marker with a fixed value of 0xF5                        │
  93 ├─────────┼───────────────────────────────────────────────────────────────┤
  94 │0x01/0x02│Image width (0x80) encoded as big-endian                       │
  95 ├─────────┼───────────────────────────────────────────────────────────────┤
  96 │0x03/0x04│Image height (0x80) encoded as big-endian                      │
  97 ├─────────┼───────────────────────────────────────────────────────────────┤
  98 │0x05/0x06│Number of 8x8 blocks in the image (0x100) encoded as big-endian│
  99 ├─────────┼───────────────────────────────────────────────────────────────┤
 100 │0x07     │Shuffle pattern to use                                         │
 101 ├─────────┼───────────────────────────────────────────────────────────────┤
 102 │0x08     │Unknown, bits 1 and 2 carry some special meaning. Usually      │
 103 │         │contains value 0x04.                                           │
 104 ├─────────┼───────────────────────────────────────────────────────────────┤
 105 │         │Related to block shuffling, exact meaning unknown. Contain 0xFF│
 106 │0x09     │for shuffle pattern 1, for other shuffle patterns it contains a│
 107 │         │value depending on the picture frame resolution. For 128x128   │
 108 │         │frames it contains 1, for 96x64 frames it contains 0.          │
 109 ├─────────┼───────────────────────────────────────────────────────────────┤
 110 │0x0A/0x0B│Length of following image data                                 │
 111 ├─────────┼───────────────────────────────────────────────────────────────┤
 112 │0x0C-0x0F│Padding/unused (all 0x00)                                      │
 113 └─────────┴───────────────────────────────────────────────────────────────┘
 114
 115 8x8 pixel block
 116
 117 The 8x8 pixel block is encoded further as a variable length block, as
 118 follows:
 119
 120 ┌──────┬───────┬──────────────────────────────────────────────────────────┐
 121 │Offset│Meaning│                          Remark                          │
 122 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 123 │      │Length │Bit 0-6 is the length of the rest of the block (often     │
 124 │0x00  │byte   │0x2F). Bit 7 selects between 2-bit and 4-bit luma decoding│
 125 │      │       │mode                                                      │
 126 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 127 │      │Luma Y │Bit 0-6 is the base offset of the luminance channel for   │
 128 │0x01  │byte   │every pixel in the block. Bit 7 selects between two       │
 129 │      │       │luminance patterns tables (LUMA1 or LUMA2)                │
 130 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 131 │      │Chroma │Bit 0-6 is the base offset of the U chrominance channel   │
 132 │0x02  │U byte │for every pixel in the block. Bit 7 indicates extended    │
 133 │      │       │decoding of this chrominance channel                      │
 134 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 135 │      │Chroma │Bit 0-6 is the base offset of the V chrominance channel   │
 136 │0x03  │V byte │for every pixel in the block. Bit 7 indicates extended    │
 137 │      │       │decoding of this chrominance channel                      │
 138 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 139 │0x04  │Chroma │Variable length chrominance channel U decoding info, see  │
 140 │      │U data │below                                                     │
 141 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 142 │...   │Chroma │Variable length chrominance channel V decoding info, see  │
 143 │      │V data │below                                                     │
 144 ├──────┼───────┼──────────────────────────────────────────────────────────┤
 145 │...   │Luma Y │Variable length luminance channel decoding info, see below│
 146 │      │data   │                                                          │
 147 └──────┴───────┴──────────────────────────────────────────────────────────┘
 148
 149 Decoding chrominance
 150
 151 Chrominance is encoded with a reduced resolution of 4x4 "pixels" per block.
 152
 153 The chrominance decoding info consists of:
 154
 155 ┌─────────┬──────────┬────────────────────────────────────────────────────┐
 156 │ Offset  │ Meaning  │                       Remark                       │
 157 ├─────────┼──────────┼────────────────────────────────────────────────────┤
 158 │         │Pattern   │Index into a color base pattern table (CHROMA). The │
 159 │0x00     │byte A    │table entry contains the pattern for the top 8      │
 160 │         │          │chroma pixels.                                      │
 161 ├─────────┼──────────┼────────────────────────────────────────────────────┤
 162 │         │Pattern   │Index into a color base pattern table (CHROMA). The │
 163 │0x01     │byte B    │table entry contains the pattern for the bottom 8   │
 164 │         │          │chroma pixels.                                      │
 165 ├─────────┼──────────┼────────────────────────────────────────────────────┤
 166 │         │          │Optional correction items for each chroma pixel     │
 167 │0x02-0x09│Correction│(using table CORR). This part is only present when  │
 168 │         │          │bit7 of the chroma byte is set.                     │
 169 └─────────┴──────────┴────────────────────────────────────────────────────┘
 170
 171 The chrominance value is basically the sum of:
 172
 173  1. chrominance base value (from the chroma U or V byte minus 0x40)
 174  2. one of the two base patterns selected from table CHROMA using pattern
 175     byte A and B.
 176  3. optionally a set of correction values selected from table CORR (very
 177     much like luminance)
 178
 179 Chroma pixels in a segment are arranged in the following pattern:
 180
 181 A00 A01 A02 A03
 182 A04 A05 A06 A07
 183 B00 B01 B02 B03
 184 B04 B05 B06 B07
 185
 186 where Axx indicates data looked up using pattern byte A, and Bxx data
 187 looked up using pattern byte B.
 188
 189 Note that the chroma info per channel (U and V) is either 2 or 10 bytes,
 190 which is why the total block size can be one of 48, 56, or 64 bytes (resp
 191 no corr, corr for 1 channel, corr for both channels). By far most blocks
 192 are 48 bytes big.
 193
 194 Decoding luminance
 195
 196 The luminance decoding info consists of:
 197
 198 ┌─────────┬───────────────────────────────────────────────────────────────┐
 199 │ Offset  │                            Meaning                            │
 200 ├─────────┼───────────────────────────────────────────────────────────────┤
 201 │0x00-0x07│A set of indexes into table LUMA1 or LUMA2 to select a "base   │
 202 │         │pattern" for each row of pixels inside a block.                │
 203 ├─────────┼───────────────────────────────────────────────────────────────┤
 204 │         │Correction items for each pixel in the block, where each       │
 205 │0x08-0x27│correction item is encoded in 4 bits. Each correction item is  │
 206 │         │actually an index into table CORR storing a value that is added│
 207 │         │to the luminance value of the pixel.                           │
 208 └─────────┴───────────────────────────────────────────────────────────────┘
 209
 210 In short, the luminance channel of each pixel is basically the sum of:
 211
 212  1. luminance base value as encoded in byte 0x01
 213  2. one of the base patterns selected from table LUMA1 or LUMA2 using bytes
 214     0x00-0x07 (one byte for one pattern per row of 8 pixels)
 215  3. one of the correction values selected from table CORR using the nibbles
 216     in bytes 0x08-0x27. This uses one nibble for each pixel, with the high
 217     4 bits (high nibble) of a byte coding the correction for the first
 218     pixel that bytes corrects, and the low 4 bits code the correction for
 219     the second pixel. The first byte (at offset 0x08), codes the correction
 220     for pixel 00 and 01, etc.
 221
 222 Pixels are arranged in the following pattern:
 223
 224 00 01 02 03 04 05 06 07
 225 08 09 0A 0B 0C 0D 0E 0F
 226 ...
 227 38 39 3A 3B 3C 3D 3E 3F
 228
 229 Color decoding
 230
 231 The color space used in the images is a kind of YUV, using one luminance
 232 channel (called Y here) and two chrominance channels (called U and V here),
 233 as follows:
 234
 235 R = 2 * (Y + V)
 236 G = 2 * (Y - U - V)
 237 B = 2 * (Y + U)
 238
 239 Any underflows/overflows during the calculation of the RGB values should be
 240 saturated to either 0 or 255 respectively.
 241
 242 And conversely (during encode):
 243
 244 Y = (R + G + B) / 6
 245 U = B/2 - Y
 246 V = R/2 - Y
 247
 248 where U and V should be constrained to the range -64 to +63.
 249
 250 Shuffling/unshuffling
 251
 252 Blocks of 8x8 pixels are stored in a shuffled sequence. The choice of the
 253 shuffle pattern is stored in byte 0x07 of the image header.
 254
 255 The shuffle pattern is stored in table SHUFFLEx, which contains the (x,y)
 256 coordinates of each 8x8 pixel block. Currently there are 7 known shuffle
 257 patterns.
 258
 259 Table overview
 260
 261 Several tables are involved in encoding/decoding. Below is an overview of
 262 the various tables, their properties and what they are used for
 263
 264 ┌────────┬────────────┬───────────────────────────────────────────────────┐
 265 │ Table  │ Dimension  │                      Remark                       │
 266 ├────────┼────────────┼───────────────────────────────────────────────────┤
 267 │        │256 entries │Entry contains brightness patterns for 1 row of 8  │
 268 │LUMA1   │of 8 signed │pixels within an 8x8 block.                        │
 269 │        │words       │                                                   │
 270 ├────────┼────────────┼───────────────────────────────────────────────────┤
 271 │        │256 entries │Entry contains brightness patterns for 1 row of 8  │
 272 │LUMA2   │of 8 signed │pixels within an 8x8 block. Alternate table.       │
 273 │        │words       │                                                   │
 274 ├────────┼────────────┼───────────────────────────────────────────────────┤
 275 │        │256 entries │Entry contains chroma patterns for 2 rows of 4     │
 276 │CHROMA  │of 8 signed │pixels within an 4x4 chroma block.                 │
 277 │        │words       │                                                   │
 278 ├────────┼────────────┼───────────────────────────────────────────────────┤
 279 │        │256 entries │Entry contains the (x,y) coordinates for an 8x8    │
 280 │SHUFFLEx│of 2 bytes  │block. There are several tables like this, each one│
 281 │        │            │encoding for a different shuffle pattern.          │
 282 ├────────┼────────────┼───────────────────────────────────────────────────┤
 283 │        │16 entries  │Correction values that are applied for each pixel. │
 284 │CORR    │of 1 signed │Values in this table:                              │
 285 │        │word        │-26,-22,-18,-14,-11,-7,-4,-1,1,4,7,11,14,18,22,26  │
 286 └────────┴────────────┴───────────────────────────────────────────────────┘
 287
 288 The LUMA1, LUMA2 and CHROMA tables are stored inside the picframe in 16
 289 bits signed (2's complement) LE byte order format. LUMA1 starts at 0x8477,
 290 LUMA2 at 0x9477, CHROMA at 0xA477. These 3 tables are directly followed at
 291 0xB477 by various shuffle tables, which contain x, y coordinate pairs (1
 292 byte for each). There are a number of sets of shuffle tables, for different
 293 display resolutions. There are 8 or 7 tables per set, the first 2 tables
 294 are "generated" (0 = row by row, 1 = column by column), then 6 or 5 tables
 295 per resolution in ROM:
 296
 297 ┌──────────┬──────┬─────────────────────┐
 298 │Resolution│start │Number of sets in ROM│
 299 ├──────────┼──────┼─────────────────────┤
 300 │128 x 160 │0xB477│6                    │
 301 ├──────────┼──────┼─────────────────────┤
 302 │128 x 128 │0xC377│5                    │
 303 ├──────────┼──────┼─────────────────────┤
 304 │120 x 160 │0xCD77│5                    │
 305 ├──────────┼──────┼─────────────────────┤
 306 │96 x 64   │0xD92F│5                    │
 307 └──────────┴──────┴─────────────────────┘
 308
 309 Retrieved from "http://picframe.spritesserver.nl/wiki/index.php/
 310 ImageEncoding"
 311
 312 Powered by MediaWiki
 313 GNU Free Documentation License 1.2
 314
 315   • This page was last modified 20:49, 16 March 2010.
 316   • This page has been accessed 4,256 times.
 317   • Content is available under GNU Free Documentation License 1.2.