home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / formats / gif / encdat.asc < prev    next >
Encoding:
Text File  |  1988-03-21  |  8.6 KB  |  223 lines
  1.  
  2. Notes on GIF Data Structures
  3.  
  4. Jake Lund  76703,3051
  5.  
  6.  
  7. This is a brief explanation of fast and memory-efficient tree 
  8. technique for encoding GIF pictures.  It could easily be adapted 
  9. to GIF decoding.  I wrote the encoder in 6502 assembly language 
  10. for the Commodore 64, but the idea is general enough that it could 
  11. be written in any language.
  12.  
  13.      I've looked at other GIF encoders/decoders and when I see a 
  14. series of weird multiplies and adds I know a hash table is coming 
  15. up.  I don't like hash tables.  They use up more memory than they 
  16. should and there's always a problem with resolving collisions.  
  17. Hash tables are sloppy.  Now that I've said that, here's the tree 
  18. that avoids hashing...
  19.  
  20.      GIF codes can be up to 12 bits long (4096).  The table has to 
  21. accommodate up to 4096 codes and this technique needs only five 
  22. bytes per code (at most a little over 20K of memory, which easily 
  23. fits in a 64 or almost any other computer).
  24.  
  25.      First, you have to imagine memory being split up into five-
  26. byte chunks, each of which is called a "record".  Each record has 
  27. a "record number," and records are stored sequentially according 
  28. to their record numbers.  If you were doing this in C, you'd need 
  29. a one-dimensional array of structures where each struct had a one-
  30. byte char and two two-byte ints.  Record numbers start at zero.
  31.  
  32.      Let's say 16384 (hex $4000) is where the code table resides.  
  33. Record 0 is at 16384, record 1 is at 16384+5, record 2 is at 
  34. 16384+10, and so on.  You also need a five-byte buffer and two 
  35. routines: one for copying the buffer up to a specific address in 
  36. memory and one for copying a record down to the buffer.  In 
  37. assembly, you shift left twice (times four), add the original 
  38. record, and add the address of the table.
  39.  
  40.      Each record is arranged like this:
  41.  
  42.      Byte 0: The "name"
  43.      Bytes 1-2: The record # for the "oldest child"
  44.      Bytes 3-4: The record # for the "next-youngest sibling"
  45.  
  46.      If the child is zero, it means there is no child.  Likewise 
  47. for the sibling.
  48.  
  49.      When you add a new record, you give it a name, but you also 
  50. mark it as having no children or siblings.  At the same time, you 
  51. have to go back to the parent or older sibling and link in the new 
  52. arrival.
  53.  
  54.      At the beginning of an encoding session, you already know the 
  55. palette and its size.  If you have 16 colors, records 0-15 
  56. correspond to the original colors.  Records 16 and 17 are reserved 
  57. for the "clear table" and the "end of picture" codes.  The next 
  58. available record (NEXT) would be 18.  When you start a new picture 
  59. (or encounter a clear table code), you have to clear the root 
  60. entries (0-15 or whatever) so they have no children and no 
  61. siblings.  NEXT has to be reset to 18 (or "end of picture" plus 
  62. one).
  63.  
  64.      Here's an example.  There are four colors in the palette.  
  65. The colors are ABCD (codes 0-3) and their record numbers are 0-3.  
  66. Code 4 means "clear the table" and code 5 means "end of pic."  The 
  67. next available code (NEXT) is 6.
  68.  
  69.      Let's say the color stream looks like this: ABACACCADACCD.  
  70. Get the first color (A).  It's automatically code 0 (the GIF code 
  71. at this point is 0).  Copy record 0 to the buffer and get the next 
  72. color, which is B.  Check the buffer for children.  Record 0 has 
  73. no children.  First link NEXT (record 6) as the oldest child -- 
  74. record 0 has a child 6.  Copy the buffer back to memory with the 
  75. record # of the child 6.  Child 6 has a name (B), but no children 
  76. or siblings.  Copy record 6 to memory.  Send the GIF code (0) to 
  77. the data stream.  Now we have the following situation:
  78.  
  79. .  data stream: 0
  80. .  color stream: xBACACCADACCD ("x" means the color was handled)
  81. .  last color: B
  82. .  NEXT: 7
  83. .  ancestry:  0A  1B  2C  3D
  84. .              !
  85. .             6B
  86.  
  87.      Record 6 is the oldest child of 0.  The name of record 6 is 
  88. color "B."
  89.  
  90.      The last color was B, so the GIF code is automatically 1.  
  91. Get another color, which is A.  Copy record 1 to the buffer.  It 
  92. doesn't have any kids, so record 7 (NEXT) has to be linked as the 
  93. oldest kid to record 1.  Insert $0007 in bytes 1-2 of the buffer 
  94. and copy back to the code table.  Add a record 7, with a name "A" 
  95. and no kids or siblings.
  96.  
  97. .  data stream: 0 1
  98. .  color stream: xxACACCADACCD
  99. .  last color: A
  100. .  NEXT: 8
  101. .  ancestry:  0A  1B  2C  3D
  102. .              !   !
  103. .             6B  7A
  104.  
  105.      The last color was A, so the GIF code is 0.  Get a color, 
  106. which is C and check record 0 for kids.  Aha!  It has a child, 
  107. record #6.  Copy that from memory to the buffer.  Check the name.  
  108. We want a C, but the kid's name is B.  Plus, B doesn't have any 
  109. younger siblings.  We have to add a younger brother/sister (#8) to 
  110. record 6.  Add $0008 to positions 3-4 in the buffer and copy 6 up 
  111. to memory.  Add a record #8, with a name C and no kids or 
  112. siblings.  Send out the GIF code 0.
  113.  
  114. .  data stream: 0 1 0
  115. .  color stream: xxxCACCADACCD
  116. .  last color: C
  117. .  NEXT: 9
  118. .  ancestry:  0A       1B  2C  3D
  119. .              !        !
  120. .             6B = 8C  7A
  121.  
  122.      By the way, in the tree above, the "!" means "has a child" 
  123. and the "=" means "has a younger sibling."  Records 0 and 1 have 
  124. children but no siblings.  Record 6 has a sibling but no children.  
  125. Records 2, 3, 7, and 8 have no kids and no siblings.
  126.  
  127.      The current/last color was C (root record #2) and the next 
  128. color is A.  C doesn't have any kids, so we add A as the oldest 
  129. child and send out a 2.
  130.  
  131. .  data stream: 0 1 0 2
  132. .  color stream: xxxxACCADACCD
  133. .  last color: A
  134. .  NEXT: 10
  135. .  ancestry:  0A       1B  2C  3D
  136. .              !        !   !
  137. .             6B = 8C  7A  9A
  138.  
  139.      Now it gets interesting.  We've got an A (GIF code 0).  The 
  140. next incoming color is a C.  A has at least one child, so we check 
  141. record 6.  Doesn't match.  The name of 6 is B and we want a C.  
  142. But record 6 has a sibling record 8.  Copy 8 down to the buffer.  
  143. Bingo!  The name matches, so there's a new GIF code (8).  Loop 
  144. back to the get-a-color routine.  The next one is C.  That's no 
  145. good because record 8 has no offspring.  So the program does three 
  146. things: 1) add NEXT (record 10) as the child of record 8, 2) add 
  147. record 10 to memory (name C, no kids or siblings), 3) send out GIF 
  148. code 8.
  149.  
  150. .  data stream: 0 1 0 2 8
  151. .  color stream: xxxxxxCADACCD
  152. .  last color: C
  153. .  NEXT: 11
  154. .  ancestry:  0A       1B  2C  3D
  155. .              !        !   !
  156. .             6B = 8C  7A  9A
  157. .                   !
  158. .                 10C
  159.  
  160.      The last color was C.  The GIF code is 2.  Get another color, 
  161. which is A.  Does record 2 have children?  Yes, record 9.  The 
  162. name of 9 is A, which is exactly what we need.  The new GIF code 
  163. is 9 and we get a color (D).  Record 9 has no kids, so insert the 
  164. number 11 as the child of 9.  Add record 11 (name D, no kids or 
  165. siblings).  Send out a GIF code 9.
  166.  
  167. .  data stream: 0 1 0 2 8 9
  168. .  color stream: xxxxxxxxDACCD
  169. .  last color: D
  170. .  NEXT: 12
  171. .  ancestry:  0A       1B  2C  3D
  172. .              !        !   !
  173. .             6B = 8C  7A  9A
  174. .                   !       !
  175. .                 10C     11D
  176.  
  177.      Last color was D.  GIF code 3.  Get a new color (A).  Record 
  178. 3 has no kids, so A is added.  Record 3 now has a child 12.  
  179. Record 12 has a name A but no kids or brothers/sisters.  Send out 
  180. the GIF code 3.
  181.  
  182. .  data stream: 0 1 0 2 8 9 3
  183. .  color stream: xxxxxxxxxACCD
  184. .  last color: A
  185. .  NEXT: 13
  186. .  ancestry:  0A       1B  2C   3D
  187. .              !        !   !    !
  188. .             6B = 8C  7A  9A  12A
  189. .                   !       !
  190. .                 10C     11D
  191.  
  192.      Start with A.  GIF code 0.  Record 0 has a child 6 (name B), 
  193. which is wrong, but 6 has a sibling 8 (name C), which is right.  
  194. The GIF code is 8.  Next color is C.  Record 8 has a child 10 
  195. (name C), which matches.  The GIF code is 10.  Record 10 has no 
  196. kids or siblings, so 1) add 13 as the child of 10, 2) add record 
  197. 13 with the name D (no children or siblings), and 3) send out GIF 
  198. code 10.
  199.  
  200. .  data stream: 0 1 0 2 8 9 3 10
  201. .  color stream: xxxxxxxxxxxxD
  202. .  last color: D
  203. .  NEXT: 14
  204. .  ancestry:  0A       1B  2C   3D
  205. .              !        !   !    !
  206. .             6B = 8C  7A  9A  12A
  207. .                   !       !
  208. .                 10C     11D
  209. .                   !
  210. .                 13D
  211.  
  212.      The encoding would continue from there.  Decoding would be 
  213. even easier (all you need is a name and a parent).
  214.  
  215.      I hope this explanation was understandable.  By the way, the 
  216. Commodore 64 encoder is only about 1.5K of assembly language.  
  217. With a little tweaking, we should be able to shrink it down to 
  218. about 1K.
  219.  
  220.      Jake Lund 76703,3051
  221.  
  222.  
  223.