Problem with bits in byte array....


Closed Thread
Results 1 to 16 of 16
  1. #1
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517

    Default Problem with bits in byte array....

    Hi,
    I've stared at this for most part of the day, re-written, made testcases etc etc without coming closer to the problem, I really need a fresh pair of eyes on this.

    What I'm working on is a BASE64 encoder for the SMTP-engine of the W5100 project. I had it working nicely (and I can revert if this doesn't work out) but I was trying to save some RAM and ended up in this mess. Basically what I'm trying to do is copying bits from one place in to another in an array of bytes. The array is currently 256 bytes long and I'm trying to copy data from the start of it to middle - bit by bit.

    Here's the current test-case code to demonstrate the problem:
    Code:
    BufferLength    CON 256
    BufferOffset    CON BufferLength/2
    Buffer          VAR Byte[BufferLength]
    ByteCount       VAR BYTE
    GetBit          VAR WORD
    PutBit          VAR WORD
    BitCount        VAR BYTE
    BufferByteIndex VAR BYTE
    BufferBitIndex  VAR BYTE
    Temp            VAR BIT
    i               VAR BYTE
    
    ByteCount = 0
    BitCount = 7
    
    'Preload the Buffer array with the text 123
    ArrayWrite Buffer,["123",0]
    
    BufferByteIndex = BufferOffset
    
    HSEROUT["BufferByteIndex: ", DEC BufferByteIndex,13]    
    
        ' We're just doing three bytes for this test.
        While ByteCount < 3
            Buffer[BufferByteIndex] = 0                 ' Clear current "out-byte" (should be 128, 129,130, 131)
            HSEROUT["Buffer[", DEC BufferByteIndex, "]=", DEC Buffer[BufferByteIndex],13]
       
            ' Do it in chunks of 6 bits.
            For BufferBitIndex = 5 to 0 Step -1
                
                ' Calculate where to get the bit
                Getbit = ByteCount * 8 + BitCount
                
                'Calculate where to put the bit
                Putbit = BufferByteIndex * 8 + BufferBitIndex
                
                
                HSEROUT["Read Byte ", #ByteCount, ".", DEC BitCount, " (GetBit=", DEC Getbit, ")"]
                HSEROUT[". Write byte ", #BufferByteIndex, ".", DEC BufferBitIndex]
                HSEROUT[" (PutBit=", DEC Putbit, ").  Bitstate is: ", DEC Buffer.0[Getbit] ]
                
                Temp = Buffer.0[GetBit]
                HSEROUT[" Temp: ", DEC Temp,13]
    '-----------------------------------------------------------------------------------
    '            Buffer.0[Putbit] = Temp
    '            HSEROUT["  Reading back: ", DEC Buffer.0[Putbit],13]
    '-----------------------------------------------------------------------------------
                
                BitCount = BitCount - 1                 ' Next bit in original string
            
                If BitCount = 255 THEN                  ' All bits in byte are processed
                    ByteCount = ByteCount + 1           ' Point to next byte
                    BitCount = 7                        ' Start at bit 7
                ENDIF
            
            NEXT    
    
            BufferByteIndex = BufferByteIndex + 1       ' Next byte in "Output string".
    
        Wend
        
        ' Display the content of the low end of buffer
        HSEROUT["Buffer[0] to Buffer[2]: "]
        For i = 0 to 2
            HSEROUT[DEC Buffer[i],","]
        NEXT
        
        'Display the content in the middle of the buffer
        HSEROUT [13, "Buffer [128] to [131]: "]
        For i = 128 to 131
            HSEROUT[DEC Buffer[i],","]
        NEXT
    
        HSEROUT [13]
        
    Pause 100
    END
    Now, the output of this code looks like this:
    Name:  Test_1.jpg
Views: 802
Size:  176.0 KB

    The purpose is to copy the bits from the low end of the array to the middle of it in chunks of 6bits. The 6 high bits of the first byte ends up in the 6 low bits of byte 128, the next 6bits ends up in the low end of byte 129 and next 6 bits in the low end of byte 130 and so on. The above screenshot indicates that all the calculations are correct, ie where it should get the bit and where it should put it. However the code actually doing the getting and putting is commented out:
    Code:
    '-----------------------------------------------------------------------------------
    '            Buffer.0[Putbit] = Temp
    '            HSEROUT["  Reading back: ", DEC Buffer.0[Putbit],13]
    '-----------------------------------------------------------------------------------
    If I uncomment these two lines everything breaks. Not only does it not work but it destorys the original data in the low end of array:
    Name:  Test2.jpg
Views: 1014
Size:  196.8 KB


    Like I said, I've stared at this for most part of the day and I just don't understand what's going on. Does anyone see anything weird, strange or even better something that's just wrong?

    Thank you in advance!

    /Henrik.

  2. #2


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    how about.....
    ? Putbit = BufferByteIndex * 8 + BufferBitIndex

    BufferByteIndex * 8 + BufferBitIndex = Putbit (put bit in array)

  3. #3


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    how about....

    ? Putbit = BufferByteIndex * 8 + BufferBitIndex

    BufferByteIndex * 8 + BufferBitIndex = Putbit (put bit into array)

  4. #4
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Hi,
    Not sure I follow you Don,
    PutBit is (or is supposed to be) the adress or bit offset into the array, Temp is the logical state to be written to that location. I don't see anything being written to the array in your proposed approach or am I missing something?

    Late last night I made some further tests and at the time it seemed like indexing bits >255 doesn't work....can anyone confirm this? In Melanies classic bits and bytes post/article she mentions using a WORD (PutBit in my case) to index bits in an array of bytes so I would have (did) thought it should work.Anyone knows?

    Thanks!
    /Henrik.

  5. #5


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    sorry, I missed where you commented out etc...

    But, in your declare
    Bufferlength con 256 (sets bit 9) 255 is max for byte and
    Buffer VAR Byte[BufferLength] might be set to 0
    Don

  6. #6
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Thanks, but the section covering arrays in the manual says:
    On PIC18 devices, byte, word and long-sized arrays are only limited in length by the amount of available memory. The compiler will assure that arrays, as well as
    simple variables, will fit in memory before successfully compiling.
    My example allocates 265 bytes and one bit, add to that the PBP system vars. It should easily fit in the 1536bytes in the 18F25K20, which is what I'm using by the way, and I'm not getting any errors or warnings.

    My "index-pointers" are WORD sized (becauae I have 256*8=2048 bits in the array) but currently it looks like I can't index bits beyond the 32'nd byte (ie when the index pointer is >255). I haven't seen anyone mention this limitation so I'm not saying this is the case (and I really hope it's not) but currently it's the only thing I can think of.

    Thanks!
    /Henrik.

  7. #7


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    OK,
    '
    Code:
     Buffer.0[Putbit] = Temp
    should it be Buffer.0(Putbit) = Temp
    [, vs (

  8. #8
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Thanks Don,
    No, both [] and () should work as far as I know. I tried and it didn't make a difference.

    The problem definitely is in the bit-indexing not allowing me to index above 255....

    Take a look at this example:
    Code:
    Buffer VAR BYTE[256]
    Index VAR WORD
    
    CLEAR
    
    HSEROUT["Buffer[32]: ", DEC Buffer[32],13]
    
    Buffer.0[256] = 1        ' Set LSB of Buffer[32]
    HSEROUT["Buffer[32]: ", DEC Buffer[32],13]
    
    Index = 256
    Buffer.0[Index] = 0     ' Clear LSB of Buffer[32]
    HSEROUT["Buffer[32]: ", DEC Buffer[32],13]
    
    Pause 100
    END
    It gives the following results:

    Name:  Byte_array_problem.jpg
Views: 727
Size:  25.5 KB

    As you can see, direct/literal indexing the 256'th bit works but doing it thru a variable doesn't. In Melanies example (which may be in error) she states that it should be possible to index bits above 255 this way (as long as the indexing variables is WORD, which it is in my case).

    I have no problem index bytes (as bytes) above 255, it's just this bit-indexing that is screwing with me.

    /Henrik.

  9. #9


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Henrik, thankyou too for explanation.
    A little different approach...........

    1, take 3 bytes at a time (from low array) and place into a LONG, lower 3 bytes, (zero high byte)
    2, left-shift 6 bits, (puts next 6 bits alone in highbyte) place highbyte into array 1/2 way up, clear highbyte, shift again.........
    for a total of 4 times (unpacks 3 base64 packed bytes to 4 bytes as you layed out)
    3, load next 3 bytes to long etc........................up to end

    not sure about padding at the part to have the correct unpacked string.

    Don

  10. #10
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Hi Don,
    Thank you but I'm doing my very best to avoid LONGs, the code produced by the long version of the compiler is much bigger than the normal even if you're not actually using a single LONG variable. So, I will do my very best to avoid using LONGs as LONG as I can ;-)

    It's not that it can't be done in another way, I had just settled on this and it had me cornered for a while. Now I know what the problem is and I'll aproach it from another angle. Had I bothered to look further back in the manual than the section on arrays I would've found this:
    7.6.4 Accessing Arrays as Multiple Variable-Types
    It is possible for a single array to be declared with multiple names and for each name to be assigned a different variable type. Note that offset for BITs are limited to a maximum value of 255
    To me, that statement is a little vague... I'm indexing a BYTE-array but on a bit basis so the above may apply (apparently) but it DOES work when "manually" indexing it:
    Code:
    Buffer VAR BYTE[64]
    Index VAR WORD
    
    Index=256
    Buffer.0[256] = 1  'Works
    Buffer.0[Index] = 0  ' Doesn't work
    Time to rethink this.

    /Henrik.

  11. #11


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    OK then, good info,
    I know you can create any of this, but trying to be helpfull,
    THIS.....
    -manipulates 2 words to unpack (thats what VB calls it)
    3 bytes from low array to 4 bytes of 6 bit each in
    other array , needs indexing to move to next 3 and 4 locations
    -The mid byte of the 24 bit Base64 is in W1 and W2 since it is used in destination byte 2 and 3
    -only 140 bytes as is to do 24bit at a time.


    Code:
    arr1 var byte[8]   'base64 packed array or part of array
    arr2 var byte[12]  ' array to unpack into
    w1 var word
    w2 var word
    ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
     
          
    w1= arr1[1]
    w2= arr1[2]
    w1= w1 >> 2
    arr2[1]=w1.byte0 & 63
    w1=w1 >> 2
    arr2[2]= w1.byte1 & 63
    arr2[4]=w2.byte1 & 63
    w2=w2 << 2
    arr2[3]= w2.byte0 & 63
    Don

  12. #12
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Thank you Don,
    Your help is much appreciated, I hope it doesn't look or feel that it's not!

    I'll give that code a try as it does look tighter than the one I'm currently trying in my effort to avoid the bit-indexing.

    /Henrik.

  13. #13


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    A visual of the routine.......

    Name:  Capture20.JPG
Views: 739
Size:  58.2 KB

    Don

  14. #14
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Hi Don,
    Thanks for that. I've tried to figure your code out without much luck, that visual representation helps me understand how you intend it to work. First I got thrown off by the arrays not being indexed from 0 and I thoght that was by intention (some trick) to make it work but now I'm not sure and I have to ask if you tried it?

    If I load arr1 with 77,97,110 I expect to get 19,22,5,46 (taken from Wikipedias example) but instead I get 19,0,4,0.

    The reason, I think, is that you're trying to load two bytes from the array into one word in one go with w1=arr1[1] etc.

    /Henrik.

    EDIT: It's not near as small as yours but this works for me:
    Code:
        Out[0] = ((In[0] >> 2) & 63)
        Out[1] = ((In[0] & 3) << 4) + ((In[1] & 240) >> 4) & 63
        Out[2] = ((In[1] & 15) << 2) + ((In[2] & 192) >> 6) & 63
        Out[3] = (In[2] & 63)
    Last edited by HenrikOlsson; - 18th October 2011 at 21:47.

  15. #15


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Henrik,
    Yes, I mistakingly was thinking that some 'W=' takes the two consecutive bytes. Also array[0] and [1] confuses me at times with for-next etc. so I just consider array start at [1].
    What you coded is good. The top and bottom (out[0] and out[3]) are simple but the ones where the 6 bit straddle 2 bytes take a little more. I tried to follow your calc on out[2] but my brain started smoking. Just wondering if '+' changes the value as opposed to the '>>' and '<<' and &. But, if it works, never argue with success.
    Anyway, thats all a relatively small simple code.
    Don

  16. #16
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,517


    Did you find this post helpful? Yes | No

    Default Re: Problem with bits in byte array....

    Let's take the Wikipedia example where they show Man being encoded:
    Code:
      In[0]    In[1]   In[2]
    01001101.01100001.01101110
    The bytes we are interested in, in the case of Out[2] are marked in red. We can break the line down in steps, making it easier to see what's going on.

    Code:
    Out[2] = In[1] & 15          ' Isolate the 4 lower bits (Out[2] now equals %00000001)
    Out[2] = In[1] = In[1] << 2  ' Shift "up" two steps (Out[2] now equals %00000100)
    Temp = (In[2] & 192)         ' Isolate the 2 top bits in In[2] (Temp now equals %01000000)
    Temp = In[2] >> 6            ' Shift it down 6 steps (Temp now equals %00000001)
    Out[2] = Out[2] + Temp       ' Add the two together (Out[2] now equals %00000101)
    Out[2] = Out[2] & 63         ' Isolate the 6 lower bits
    In fact, I wonder if the last step is actually needed....depends on what gets "shifted in" at the top but I guess that "should" be all zeros - perhaps room for improvement there....

    /Henrik.

Members who have read this thread : 1

You do not have permission to view the list of names.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts