Vmelkon
There is not a lot of point in responding to six year old posts on talk pages on issues which have already been dealt with long ago. You are only succeeding in unnecessarily triggering people's watchlists. Anyway, here is a welcome message;
Welcome...
Hello, Vmelkon, and welcome to Wikipedia! Thank you for your contributions. I hope you like this place and decide to stay. Here are some pages that you might find helpful:
- Introduction
- The five pillars of Wikipedia
- How to edit a page
- Help
- How to write a great article
- Manual of Style
Please sign your name on talk pages using four tildes (~~~~); this will automatically produce your username and the date. If you need help, check out Wikipedia:Questions, ask me on my talk page, or place {{helpme}} on your talk page and ask your question there. Again, welcome! SpinningSpark 08:36, 26 June 2011 (UTC)
GIF format
editVmelkon wrote: I am writing a GIF file reader/writer. I can't make sense of this crazy file format. When there is only 1 image block, I am able to read it ok. However, if the compressed data is over 256 bytes, it becomes a problem. I can see that it is using a 9 bit encoding. So, a maximum value of 511 (decimal). As a test, I made a large blue image. I can see the compressed values slowly rise to 511 but then, it is 0, 3, 10, 28, 72, ... That doesn't make sense. It should be 257 to clear the table. Then, 256 to start a new table. Then the data should start again as 0, 258, 259 all the way to 511 again. Can anyone help? Vmelkon (talk) 17:54, 10 February 2018 (UTC)
- Hi -- I moved your comment here from the GIF talk page, where it's not really appropriate. I can't tell from your description of the problem just what is going wrong. So I'll just make a few observations.
- While code 256 is used to clear the encoding table, code 257 is just a stop code: it's used only at the end of an image, not to start a new table. A new table is automatically started after code 256.
- I'm not sure what you mean by "1 image block". Does this mean "1 image in the file" (i.e., only one Image Descriptor) or "1 sub-block of 256 bytes in the sub-block chain" (a very short single image)?
- People typically run into trouble when breaking the image data into 256-byte sub-blocks. The encoded data is 9 bits (or greater) per pixel, and the boundaries of the coded values typically do not match the sub-block boundaries, so that a single encoded value must be split across the sub-block boundaries. (You cannot pad the image data with 0 bits except after the stop code.)
- -- Elphion (talk) 18:29, 10 February 2018 (UTC)
- Thanks for the reply. I guess you are calling it a sub-block while I called it a image block. I just understood what this wacky format does. It starts as 9 bit encoding, which gives a maximum value of 511 (decimal). Then, it switches to 10 bit! So, it continues as 512, 513, 514 and so on. I guess it goes to a maximum of 1023 and then switches to 11 bits. This happens because like I said, I made a large blue image (any solid color will do). Vmelkon (talk) 22:50, 11 February 2018 (UTC)
- Yes, when the encoder generates the first 10-bit code (2^9) in its table, it emits the current output code at 9 bits and then switches to 10-bit width for future output (even though it may be a while later before a value >= 2^9 is actually emitted as output). Likewise, it eventually adjusts the output size to 11 and 12 bits as the table codes get larger. GIF caps the the code length at 12 bits, so larger values are not entered into the table or emitted as output. As the decoder is always one step behind the encoder, it has to increase the code width from 9 to 10 when it generates the last 9-bit value (2^9 − 1) in its table. It's not exactly wacky: 9 bits is not enough for significant compression, but 12 bits requires too much space for the early part of the image, where the codes are always shorter. So the variable-width codes are part of the space-saving technique. -- Elphion (talk) 06:49, 12 February 2018 (UTC)
- I was expecting for them to use the value of 257 as a stop signal. I was expecting the process to restart. So, what followed 1 1111 1111 (511) was actually 0 0000 0000 and I was confused. It turns out it switches to 10 bits. The value there was 10 0000 0000 (512). I could not make heads or tails for days so I abandoned this for months. They really should put that in large letters in the specification since it is not intuitive at all. If someone makes a huge blue image, how am I suppose to handle it if it caps off at 12 bits? What if there is a need for more? Vmelkon (talk) 02:57, 13 February 2018 (UTC)
- Yes, when the encoder generates the first 10-bit code (2^9) in its table, it emits the current output code at 9 bits and then switches to 10-bit width for future output (even though it may be a while later before a value >= 2^9 is actually emitted as output). Likewise, it eventually adjusts the output size to 11 and 12 bits as the table codes get larger. GIF caps the the code length at 12 bits, so larger values are not entered into the table or emitted as output. As the decoder is always one step behind the encoder, it has to increase the code width from 9 to 10 when it generates the last 9-bit value (2^9 − 1) in its table. It's not exactly wacky: 9 bits is not enough for significant compression, but 12 bits requires too much space for the early part of the image, where the codes are always shorter. So the variable-width codes are part of the space-saving technique. -- Elphion (talk) 06:49, 12 February 2018 (UTC)
- When you reach the end of the 12-bit codes, you can either clear the table and start filling it again (which buys you nothing for a solid blue image), or you can simply stop adding codes to the table -- it will still work, you just don't get any larger codes. Remember that the format was designed for internet images in the 80s: i.e., relatively small ones. Also, there's a trade-off with the code width: if you allow much more than 12 bits, the table starts to get large and unwieldy. Back in those days, there wasn't a lot of memory available. -- Elphion (talk) 05:37, 13 February 2018 (UTC)
- Thanks for the reply Elphion. I had to add the various 10 bit functions to handle 10 bit. I also decided to convert the 9 bit part to 10 bit when I see the value of 511 and the array has more elements, then I concatenate the rest of the array which is already 10 bit. So, I upgrade the entire array to 10 bit, then I decompress the LZW compressed values with my 10 bit decompressor function. It worked. I can open my 500x500 blue image. ANYWAY, I encountered an image with a 7 bit encoding. I don't get it. How am I suppose to decompress this? Vmelkon (talk) 15:32, 25 February 2018 (UTC)
- When you reach the end of the 12-bit codes, you can either clear the table and start filling it again (which buys you nothing for a solid blue image), or you can simply stop adding codes to the table -- it will still work, you just don't get any larger codes. Remember that the format was designed for internet images in the 80s: i.e., relatively small ones. Also, there's a trade-off with the code width: if you allow much more than 12 bits, the table starts to get large and unwieldy. Back in those days, there wasn't a lot of memory available. -- Elphion (talk) 05:37, 13 February 2018 (UTC)
It works the same way. If N is the data size declared at the beginning of the image data (so 2 <= N <= 8), then the unencoded symbols (the plaintext characters) must fall in the range 0 to (2^N)-1. The initial code length is N+1 bits, the single data characters get codes 0..(2^N)-1, the clear code is 2^N, the stop code is (2^N)+1, and new codes start at (2^N)+2. When you run out of (N+1)-bit codes, you switch to width N+2, etc up to a maximum of 12-bits. -- Elphion (talk) 19:41, 25 February 2018 (UTC)
- I see, so with 7 bit, 0 to 63 is reserved and 64 is like the 256 in the 9 bit case and 65 is like the 257. This means that we can have 64 possible pallette entries.Vmelkon (talk) 02:28, 27 February 2018 (UTC)
- Yes. You can actually have up to 256 palette entries, but only the first 64 of them can be addressed by the coded values from this image segment. You might, for example, sort the global table so the most frequent colors are first, then use a small N in an image segment for most of the canvas, and a larger N for small image segments that overwrite the parts using less frequent colors. Lots of tricks like that are used to save space, especially in animated GIFs.
- Unfortunately, I am not able to read other GIF images yet. It worked on the 500x500 blue image because I look for the value of 511 (9 bit) and what follows is 512 in 10 bit. I did the same with a colorful image by searching for 511 but the 10 bit values that come after seems to be junk. Perhaps it doesn't immediately switch to 10 bit? I don't know. Have you written a GIF file reader? Vmelkon (talk) 01:14, 1 March 2018 (UTC)
- Yes. You can actually have up to 256 palette entries, but only the first 64 of them can be addressed by the coded values from this image segment. You might, for example, sort the global table so the most frequent colors are first, then use a small N in an image segment for most of the canvas, and a larger N for small image segments that overwrite the parts using less frequent colors. Lots of tricks like that are used to save space, especially in animated GIFs.
- When you say "searching for 511", do you mean searching the codes in the data stream for 511? That's not the right answer: the encoder switches to 10 bits after it adds 512 to its dictionary, but the code value it writes at that point in general won't be 511 -- indeed, you might never see 511 produced as a code in output. Basically, the decoder has to construct the table as it processes the image, and must switch to 10 bits after it generates 511 in its dictionary, not when it *sees* 511 in the code stream. -- Elphion (talk) 04:29, 1 March 2018 (UTC)
- The thing to keep in mind is that the encoder creates a code when it sees an example of a string that is not already in the dictionary -- but that string might never appear again in the plaintext, so the code created at that point may never get used. So in general, there will be many codes in the dictionary that never appear among the output codes. An image of just one color is quite atypical in that regard, since the codes added to the dictionary *do* get used right away. -- Elphion (talk) 04:38, 1 March 2018 (UTC)
- This seems overly complicated. This is way off course from a simple LZW algorithm. I have written the LZW compression function myself but could not figure out how to decompress so I downloaded from the web and the page said it is the original published in a 1988 magazine. It doesn't handle a switch from 9 bit to 10 bit to 11 bit to 12 bit. I presume the prefix_code[] array they are using holds the table. The code looks like this (This is my version):
sint DecodeString_Universal(uchar *buffer, uint code, sint &k, uint max_code, uint *prefix_code, uint *append_character)
{
uint i;
i=0;
while(code>255)
{
buffer[k]=(uchar)append_character[code];
k++;
code=prefix_code[code];
if(i>=max_code) //We don't need this part
{
//printf("Fatal error during code expansion.\n");
return -1;
}
i++;
}
buffer[k]=(uchar)code;
return 1;
}
Any ideas? But it isn't in that function that they write to prefix_code[]. That part is elsewhere. Vmelkon (talk) 02:06, 2 March 2018 (UTC)
- This snippet just takes care of converting a code to a string. (I took the liberty of adding the tags to make it display correctly.) As you say, it doesn't deal with the GIF machinery of unpacking the codes -- but that's not a bad thing: the best way to organize a decoder is to keep the code pieces dealing with the GIF format and the LZW machinery separate. But the snippet also doesn't take care of *building* the LZW table, which is an essential part of the decoding process, just as for the encoding process. That's how the encoder and decoder manage to get the same code-to-string correspondence without passing the table with the data. -- Elphion (talk) 07:06, 2 March 2018 (UTC)
- Thank you for the responses so far, Elphion. I am returning to my GIF problem. I found that some GIF files, they end with a 257 and then the last code is 0. Because of that, I end up with an extra pixel when I expand the GIF file. For example, if the image is 40 x 40 = 1600 pixels, I get 1601 pixels when I decompress the GIF. So, I decided to throw away the 0 in those cases. I have no idea why some GIFs are like that. There is more to do. I will let you know. Thank you so far. Vmelkon (talk) 17:10, 12 April 2018 (UTC)
- 257 is the stop code: you should ignore anything that looks like a code after that. The image data should also end with an empty sub-block (a zero byte) to signal the end of the block chain, but I presume that's not what you're talking about. -- Elphion (talk) 18:30, 12 April 2018 (UTC)
- I reread what you had written before. Sounds like the 257 comes up only once and at the end of the codes. OK, not a problem. I made some progress. I can now read an image that starts out as 9 bit (2^9), then some of the codes are 10 bit (2^10), then 2^11, and finally, it encounters the decimal 257 which is coded with 11 bits. I tried on a larger image and it starts as 9 bit, then 10 bit, then 11 bit, and 12 bit. Then, at some point, there is the decimal 256 (12 bit wide). I guess I am not sure what to do at this point. My program crashes. Can I send you the image? I have the variables next_code, new_code, character in my code. Do they mean anything to you? Vmelkon (talk) 04:10, 14 April 2018 (UTC)
- 256 (i.e 2^DATASIZE, where DATASIZE is 8 in this case) is the clear code. When you get that, retain the image you've built up so far, but reset the code size to 9 (= DATASIZE+1) and clear the table you've been building up; basically reset the decoding machinery as if you're starting from the beginning, but read the next 9 bits as the next code. This can happen several times in the image; you just reset the decoding machinery and carry on. -- Elphion (talk) 05:59, 14 April 2018 (UTC)
- Looks like I got it partially working now. I had forgotten to reset max_value and max_code when I encounter the 256. Max_value would be 511 and max_code is 510 since it goes back to 9 bit (or you seem to call it 8 bit). Another problem was in my InputCode_10bit, InputCode_11bit, InputCode_12bit because I had not completed the code. The problem now is data alignment. I thought the GIF images are 1 byte data aligned. I convert them to 4 byte data aligned (DWORD aligned). My GIFs look skewed. I am displaying it as a OpenGL texture on a rectangle. Vmelkon (talk) 17:54, 14 April 2018 (UTC)
- To clarify: DATASIZE is the value at the beginning of the image data, indicating how many bits the decoded values have (typically 8). Codes start at length DATASIZE+1 bits. Regarding alignment: the decoded GIF image is just a rectangular array of numbers, of pixel width and height as specified in the image header. (The rows are typically listed from top to bottom, although GIF does support a simple interlacing scheme.) The individual numbers range from 0 to 2^(DATASIZE-1). You use the local or global color table to convert the numbers to RGB triples (three 8-bit bytes, in order: R, G, B, specifying the 3 color values as numbers from 0 to 255). How these are translated into a display format depends on the target graphic structure (in your case the OpenGL texture object, whose details I don't know off the top of my head). Target structure may have a different number of bits for each color, and may have them in a different order, so converting the color values into the format used by the target may be necessary. -- Elphion (talk) 21:21, 14 April 2018 (UTC)
- I did some experimenting. The problem doesn't come from my OpenGL side of the code. Also, I can load other formats just fine and that part of the code has been written ages ago. It isn't a data alignment problem but sort of looks like one. If the GIF image is sufficiently big, perhaps 100 pixels height and if it is "colorful high frequency image", the skewing happens. If it is mostly a solid color, the skewing goes away. Perhaps I should step away from the code again for a while and I will figure it out eventually :).Vmelkon (talk) 04:31, 15 April 2018 (UTC)
- Looks like the problem is that there are some missing pixels. In other words, I do not quite get a rectangle array of indices. Every few lines, there are some missing values. Which means, there is something still wrong with my GIF decoder. I have to investigate it further.Vmelkon (talk) 05:20, 16 April 2018 (UTC)
- I did some experimenting. The problem doesn't come from my OpenGL side of the code. Also, I can load other formats just fine and that part of the code has been written ages ago. It isn't a data alignment problem but sort of looks like one. If the GIF image is sufficiently big, perhaps 100 pixels height and if it is "colorful high frequency image", the skewing happens. If it is mostly a solid color, the skewing goes away. Perhaps I should step away from the code again for a while and I will figure it out eventually :).Vmelkon (talk) 04:31, 15 April 2018 (UTC)
- To clarify: DATASIZE is the value at the beginning of the image data, indicating how many bits the decoded values have (typically 8). Codes start at length DATASIZE+1 bits. Regarding alignment: the decoded GIF image is just a rectangular array of numbers, of pixel width and height as specified in the image header. (The rows are typically listed from top to bottom, although GIF does support a simple interlacing scheme.) The individual numbers range from 0 to 2^(DATASIZE-1). You use the local or global color table to convert the numbers to RGB triples (three 8-bit bytes, in order: R, G, B, specifying the 3 color values as numbers from 0 to 255). How these are translated into a display format depends on the target graphic structure (in your case the OpenGL texture object, whose details I don't know off the top of my head). Target structure may have a different number of bits for each color, and may have them in a different order, so converting the color values into the format used by the target may be necessary. -- Elphion (talk) 21:21, 14 April 2018 (UTC)
- Looks like I got it partially working now. I had forgotten to reset max_value and max_code when I encounter the 256. Max_value would be 511 and max_code is 510 since it goes back to 9 bit (or you seem to call it 8 bit). Another problem was in my InputCode_10bit, InputCode_11bit, InputCode_12bit because I had not completed the code. The problem now is data alignment. I thought the GIF images are 1 byte data aligned. I convert them to 4 byte data aligned (DWORD aligned). My GIFs look skewed. I am displaying it as a OpenGL texture on a rectangle. Vmelkon (talk) 17:54, 14 April 2018 (UTC)
- 256 (i.e 2^DATASIZE, where DATASIZE is 8 in this case) is the clear code. When you get that, retain the image you've built up so far, but reset the code size to 9 (= DATASIZE+1) and clear the table you've been building up; basically reset the decoding machinery as if you're starting from the beginning, but read the next 9 bits as the next code. This can happen several times in the image; you just reset the decoding machinery and carry on. -- Elphion (talk) 05:59, 14 April 2018 (UTC)
- I reread what you had written before. Sounds like the 257 comes up only once and at the end of the codes. OK, not a problem. I made some progress. I can now read an image that starts out as 9 bit (2^9), then some of the codes are 10 bit (2^10), then 2^11, and finally, it encounters the decimal 257 which is coded with 11 bits. I tried on a larger image and it starts as 9 bit, then 10 bit, then 11 bit, and 12 bit. Then, at some point, there is the decimal 256 (12 bit wide). I guess I am not sure what to do at this point. My program crashes. Can I send you the image? I have the variables next_code, new_code, character in my code. Do they mean anything to you? Vmelkon (talk) 04:10, 14 April 2018 (UTC)
- 257 is the stop code: you should ignore anything that looks like a code after that. The image data should also end with an empty sub-block (a zero byte) to signal the end of the block chain, but I presume that's not what you're talking about. -- Elphion (talk) 18:30, 12 April 2018 (UTC)
- Thank you for the responses so far, Elphion. I am returning to my GIF problem. I found that some GIF files, they end with a 257 and then the last code is 0. Because of that, I end up with an extra pixel when I expand the GIF file. For example, if the image is 40 x 40 = 1600 pixels, I get 1601 pixels when I decompress the GIF. So, I decided to throw away the 0 in those cases. I have no idea why some GIFs are like that. There is more to do. I will let you know. Thank you so far. Vmelkon (talk) 17:10, 12 April 2018 (UTC)
Disambiguation link notification for May 1
editHi. Thank you for your recent edits. An automated process has detected that when you recently edited April Fools' Day, you added a link pointing to the disambiguation page Armenian. Such links are usually incorrect, since a disambiguation page is merely a list of unrelated topics with similar titles. (Read the FAQ • Join us at the DPL WikiProject.)
It's OK to remove this message. Also, to stop receiving these messages, follow these opt-out instructions. Thanks, DPL bot (talk) 06:03, 1 May 2022 (UTC)
May 2023
edit
Welcome to Wikipedia and thank you for your contribution(s). I am glad to see that you are discussing a topic. However, as a general rule, while user talk pages permit a small degree of generalisation, other talk pages such as Talk:Moorish Science Temple of America are strictly for discussing improvements to their associated main pages, and many of them have special instructions on the top. They are not a general discussion forum about the article's topic or any other topic. If you have questions or ideas and are not sure where to post them, consider asking at the Teahouse. I also deleted the post you replied to. Doug Weller talk 18:07, 18 May 2023 (UTC)