Advertisement
Bisqwit

Tokumaru NES Bitmap Tile Compression

Apr 30th, 2016
324
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. Explanation on how Tokumaru's tile compression algorithm works.
  2. The following is pseudo-code that implements a decompressor.
  3. Reverse engineered by Joel Yliluoma in May 2016
  4. Based on source code published by Tokumaru and released in tokumaru_tile_compression.7z in 2009
  5. Algorithm document published at: http://pastebin.com/GNnimLzX
  6.  
  7. Read byte ⇒ RemainingTileCount
  8.  
  9. Read-new-color-followup-table:
  10. ; First read the color frequency table.
  11. For colors 3‥0 in Color:
  12. ; Read how many different colors can follow the current one
  13. Read 2 bits ⇒ ColorCount[Color]
  14. If ColorCount[Color] > 0:
  15. ; Decide which colors can come next.
  16. ; NextColor0, NextColor1 and NextColor2 are the colors sorted
  17. ; in order of probability. Transition from Color to each index
  18. ; may require one bit more to express than to the previous one.
  19. A = &NextColor0[Color]
  20. B = &NextColor1[Color]
  21. C = &NextColor2[Color]
  22. Read bit pattern:
  23. Case 0: A = 1 − (Color ≥ 1) ; 1 0 0 0
  24. Case 10: A = 2 − (Color ≥ 2) ; 2 2 1 1
  25. Case 11: A = 3 − (Color ≥ 3) ; 3 3 3 2
  26. ; Determine the two other colors, that are neither Color nor A
  27. B = 0. While B=Color or B=A: B = B+1
  28. C = B+1. While C=Color or C=A: C = C+1
  29. ; If the number of colors is 2, remove A from the list.
  30. If ColorCount[Color] = 2: A,B = B,C
  31. ; Thus, the colors chosen are:
  32. ; When colors=1: A
  33. ; When colors=2: B,C
  34. ; When colors=3: A,B,C
  35.  
  36. Read-tiles:
  37. ; Assume that the previous row was all blank (color 0).
  38. Plane0 = $00
  39. Plane1 = $00
  40. SecondHalf = buffer for 8 bytes
  41.  
  42. For rownumber 0‥7 in y:
  43. ; Read the next row, unless the row just repeats.
  44. Read 1 bit ⇒ RepeatFlag
  45. If RepeatFlag = 0:
  46. ; Read the color of the first pixel.
  47. Read 2 bits ⇒ Color
  48. ; Read the colors of the other 7 pixels.
  49. ; If colors=0, done. Color is not changed, bits are not read.
  50. ; Else a bit is read; if 1, done. Color is not changed.
  51. ; Else select color0. If colors=1, done.
  52. ; Else a bit is read. If 1, select color1. If colors=2, done.
  53. ; Else a bit is read. If 1, select color2.
  54. ; In other words:
  55. ; When colors=0, the color is not changed, and no bits are read.
  56. ; When colors=1, 1 = not changed, 0 = color0.
  57. ; When colors=2, 1 = not changed, 00 = color0, 01 = color1.
  58. ; When colors=3, 1 = not changed, 00 = color0, 010 = color1, 011 = color2.
  59. For coordinate 0‥7 in x:
  60. Read bit pattern:
  61. Case ε when x=0 or ColorCount[Color]=0: Color = Color
  62. Case 1 when x>0 and ColorCount[Color]>0: Color = Color
  63. Case 0 when x>0 and ColorCount[Color]=1: Color = NextColor0[Color]
  64. Case 00 when x>0 and ColorCount[Color]>1: Color = NextColor0[Color]
  65. Case 01 when x>0 and ColorCount[Color]=2: Color = NextColor1[Color]
  66. Case 010 when x>0 and ColorCount[Color]>2: Color = NextColor1[Color]
  67. Case 011 when x>0 and ColorCount[Color]>2: Color = NextColor2[Color]
  68. Shift Color into Plane0 and Plane1
  69.  
  70. // Write out the current row:
  71. Send 1 byte ⇐ Plane0.
  72. Write Plane1 ⇒ SecondHalf[y]
  73.  
  74. ; The tile is complete. Send out the second half.
  75. Send 8 bytes ⇐ SecondHalf[0‥7].
  76.  
  77. ; If TileCount becomes 0, compression is complete and ends here.
  78. if --RemainingTileCount = 0: Return
  79.  
  80. ; Otherwise read what to do next.
  81. Read bit pattern:
  82. Case 0: Go read more tiles.
  83. Case 1: Go and read a new color-followup-table.
  84.  
  85. Bits are read and stored MSB-first.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement