# Tokumaru NES Bitmap Tile Compression

Apr 30th, 2016
324
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.
8.
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]
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.
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:
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.