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:

Attachment 6061

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:

Attachment 6062

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.

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

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

how about....

? Putbit = BufferByteIndex * 8 + BufferBitIndex

BufferByteIndex * 8 + BufferBitIndex = Putbit (put bit into 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.

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

Thanks, but the section covering arrays in the manual says:

Quote:

---

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.

OK,
'

Code:

---

Buffer.0[Putbit] = Temp

---

should it be Buffer.0(Putbit) = Temp
[, vs (

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:

Attachment 6067

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.

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

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:

Quote:

---

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.

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

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.

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

Attachment 6073

Don

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)

---

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

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.