Solved

what this function does ?

Posted on 2004-04-27
11
250 Views
Last Modified: 2010-04-02
hi all , hope all are well. i have been stuck for a long time in this code below. i am not understanding what these  two function does . i remembered you people. you might help me to understand what this two function does. ok, let me write the code first.... then question.



code 1
---------
here is a  function..........

#define BITS 12    // globally declared


input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;

  while (input_bit_count <= 24)
  {
    input_bit_buffer |=
        (unsigned long) getc(input) << (24-input_bit_count);
    input_bit_count += 8;
  }
  return_value=input_bit_buffer >> (32-BITS);
  input_bit_buffer <<= BITS;
  input_bit_count -= BITS;
  return(return_value);
}


question >> i want to know what this function  does ? can you explain little bit.



code 2
---------

here is another function but  RELATED........

output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;

  output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
  output_bit_count += BITS;
  while (output_bit_count >= 8)
  {
    putc(output_bit_buffer >> 24,output);
    output_bit_buffer <<= 8;
    output_bit_count -= 8;
  }
}


question >> i want to know what this function does ? can you explain little bit about this.


IN FACT these two are the two function of a sigle main code. i am just calling these two function.i dont understand what these two functions are  are doing.


your input are valueable to me. any kind of help is highly appreciated. waiting for response.

thanking you
0
Comment
Question by:cofactor
  • 6
  • 4
11 Comments
 
LVL 46

Expert Comment

by:Sjef Bosman
ID: 10926298
First function:
- walks 4 times (input_bit_count= 0, 8, 16, 24) through a loop,
- reads four bytes from a file and puts them into a long value, first byte read in the highest bits
- e.g when reading 4 bytes 0A, 0B, 0C, 0D from a file, the variable input_bit_buffer will contain 0A0B0C0D
- then, return_value is computed as the input_bit_buffer shifted right 20 bits, in the example:
  0A0B0C0D = 00001010 00001011 00001100 00001101 -> 00000000 00000000 00000000 10100000 = 00 00 00 A0
- input_bit_buffer is then shifted left 12 bits, so it will contain the remainder since the 12 bits moved out have been placed in return_value:
  10110000 11000000 11010000 00000000 = B0 C0 D0 00
- input_bit_count contains 32, 12 is subtracted, so its value now is 20
- and the return_value is returned (00 00 00 A0)

The NEXT time the function is used, the static variables still exist, so input_bit_buffer contains the value left behind the last time the function was used, so does input_bit_count.
- input_bit_count=20, so the loop will be entered
- a byte is read, say 0E, shifted left 4 to form 00E0, and or-ed into input_bit_buffer, which now contains
  10110000 11000000 11010000 00000000 = B0 C0 D0 00 -> 10110000 11000000 11010000 11100000 = B0 C0 D0 E0
- input_bit_count is set to 28 hence the loop stops
- return_value is set to 20 highest bits of input_bit_buffer, i.e. 00000000 00001011 00001100 00001101 = 00 0B 0C 0D
- input_bit_buffer is shifted left 12 bits, to form 00001101 00001110 00000000 00000000 = 0D 0E 00 00
- input_bit_count is set to 28 - 12 = 16
- and the computed return_value is returned (00 0B 0D 0D)

It seems that each time 20 bits are read from the inputstream. Why? I haven't the faintest, that's in the programme's logic.

The second function converts 20-bit values back to bytes, the inverse of the first function.

Hope this helps...
0
 
LVL 22

Expert Comment

by:grg99
ID: 10927502
Looks like this is a way of sending and receiving variable-bit-length data.

This is commonly used in Huffman or GIF coders and compressors, which use variable bit-length sequences.

0
 

Author Comment

by:cofactor
ID: 10929975
>>reads four bytes from a file

why r u saying four bytes ?
in the function i see     getc(input)  . getc() brings one char form a file . and one char means one byte . so, how four bytes are read ?

can you clarify this step  plz.


P.S . yes its a compression code.  it  is LZW.
0
 
LVL 46

Expert Comment

by:Sjef Bosman
ID: 10930157
The initial value of the bit counter is 0. The first time it is set to 8, then 16 then 24 and then 32 and the loop stops. In the loop, each time, a byte is read from input, so the first call to the function will read 4 bytes. The second call will read one byte (bit counter is 32, subtracted 12, so 20, then in the loop set to 28) and the third call will read two bytes (28-12= 16, in the loop to 24 and in the following pass it will be set to 32). Alternately, one and two bytes will be read.
0
 

Author Comment

by:cofactor
ID: 10934933
>>>It seems that each time 20 bits are read from the inputstream. Why? I haven't the faintest, that's in the programme's logic.

hi, i read your programming mechanism. i understood ur calculation.

WHAT THE FUNCTION RETURNS  IS IMPORTANT. so, you are saying, each time it is returning 20 bits from the file. does it returns sequentially ??? (i believe  so)

it means, first call--->first 20 bits from the file.

          second call--->next 20 bits from the file.

           third call----->next 20 bits from the file

            ......       ---->next 20 bits from the file

untill EOF comes. is this way it is returning ?

am i right?

i dont understand what would be the profit ? is it not possible to read 20 bits at one go ?

>>>Looks like this is a way of sending and receiving variable-bit-length data.

why u r saying " variable-bit-length data". as you saw above in the example, function is always sending back 20 bits from the file in each call , so how can you say it is sending "variable-bit-length data" ?

of course it may read one byte and two byte alternately in later function calls but it is always returning 20 bits.


can you give some comments why u r saying like that ?


0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
LVL 46

Accepted Solution

by:
Sjef Bosman earned 40 total points
ID: 10938369
Sorry, I said it wrong, it's not 20 bits but 12. When the content of the input_bit_buffer is shifted 32-12 places to the right, only the left 12 remain. So every time the function is called, 12 bits are returned. The first time it is 0A0 (correct above), the next time it is B0C. This is not correct in the above, it should have read:

The NEXT time the function is used, the static variables still exist, so input_bit_buffer contains the value left behind the last time the function was used, so does input_bit_count.
- input_bit_count=20, so the loop will be entered
- a byte is read, say 0E, shifted left 4 to form 00E0, and or-ed into input_bit_buffer, which now contains
  10110000 11000000 11010000 00000000 = B0 C0 D0 00 -> 10110000 11000000 11010000 11100000 = B0 C0 D0 E0
- input_bit_count is set to 28 hence the loop stops
- return_value is set to the 12 highest bits of input_bit_buffer, i.e. 00000000 00000000 00001011 00001100 = 0B 0C
- input_bit_buffer is shifted left 12 bits, to form 00001101 00001110 00000000 00000000 = 0D 0E 00 00
- input_bit_count is set to 28 - 12 = 16
- and the computed return_value is returned (B 0C)

So 12 bits. Indeed they are read until EOF, although the test on EOF is not done in the function. If you look in the manual on getc(), you see that the constant EOF is returned on end of file. I'm not sure, but I think EOF is defined as -1, so the character read is effectively set to FF. When reconstructing the original data, this should be no problem if you know the original length of the file.

Indeed it is impossible to read 12 bits, since characters are 8-bits wide, and 4-bit computers don't exist any longer. I talked about variable-bit-length data, since the constant BITS is defined as 12. For other purposes, BITS could be set to any other value and the function would read that amount of bits from the stream. In this case, 8 and 16 bits are read to form 12-bit values.

Hope I explained it somewhat better now. My apologies :)
0
 

Author Comment

by:cofactor
ID: 10938422

hi...this two function i have taken from link

 http://www.dogma.net/markn/articles/lzw/lzw.htm

the code is over there . can you tell why it is called   " .....two routines are used to output variable length  codes....."

i see that they are sending 20 bits in each call. why it is called  "variable length  codes" ?

this code is ada[ted from that link.

thanks
0
 

Author Comment

by:cofactor
ID: 10938451
oops...you are online.i did not notice your comment . you have posted early . ok..let me have a look on your comments.
0
 

Author Comment

by:cofactor
ID: 10939205
hi , i have read your explanation . you have explained very nicely.

>>"Indeed it is impossible to read 12 bits, since characters are 8-bits wide, and 4-bit computers don't exist any longer. I talked about variable-bit-length data, since the constant BITS is defined as 12. For other purposes, BITS could be set to any other value and the function would read that amount of bits from the stream. In this case, 8 and 16 bits are read to form 12-bit values"

so , you are saying as  there is  #define BITS 12 so it is a variable length so that i can set it to any varying length. right ?

i have a question on this comment . what  happens if i set    #define   BITS 12  . DOES THE program reads data  from the file faster ? is it just bcoz of this ? i dont think so, if i need to read more data i could have usued fread() to read a big chunk from the file.

i am very very curious to know  WHY   i would set the BIT= 12 or any other value ? what BENIFIT i am getting by reading the file in so complex way ? why i am not reading the file in  simple way just as we normally read.

is there any benefit really if the function returns 12 bits ?

thanks ....your  explanation was very good to read. i have given a link above. i understnad the algorithm.

can you explain my above questions.
0
 
LVL 46

Expert Comment

by:Sjef Bosman
ID: 10939341
The next line
    #define BITS 12
means that, during compile-time, wherever BITS is used in the program, 12 will be replaced by the compiler (actually the C-preprocessor). Indeed you could set this to a different value, as Mark Nelson says: "In the code accompanying this article, I have used code sizes of 12, 13, and 14 bits". When you change the value, you have to recompile the program and redistribute it (when necessary). So it's more or less fixed this way, unless you have the source code. Reading data isn't faster or slower, since everything is buffered by the standard IO-library, so using fread is not going to help. What's more, the whole processing is built around reading several bits at a time, putting them into a long and shifting them in place. You could read a lot with fread, but houw are you going to shift all those bits? I t  w i l l  b e  s l o w...

The why of setting BITS to 12 is not for me to judge. Just read Mark Nelson's article, the part about the 12/13/14 bits above. You'll see!
0
 

Author Comment

by:cofactor
ID: 10952212
ok...thanks.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now