Modular arithmetic logic

[Jinxer]

I am trying to use a ring buffer to store data. I am using an array of 56 bytes and each item of data is 8 bytes long. The following codes work

for j=0 to 7:
buffer[i+j] = newData[j]
i = (i+8) % 56

But when I changed it to 9 bytes long

for j=0 to 8:
buffer[i+j] = newData[j]
i = (i+9) % 56

it produces nonsense. I am pretty sure it’s the modular arithmetic’s problem but I am not sure why. Can someone explain the logic to me, thanks.

 

[Dr.Peterson]

What are you expecting to see, and how is the new result different from that?

Might the fact that 56 is a multiple of 8 but not of 9 explain what you are seeing?

 

[Cubist]

I guess that "i" in your pseudo code is the current insertion pointer for the ring buffer? Your buffer could easily overflow if "i=54", say, on entry into your code. (This could be the case after 6 insertions of 9 values.) Your loop just assumes the ring buffer is big enough, and will attempt to assign buffer[54] ... buffer[62] when the buffer is intended to only have locations buffer[0] ... buffer[55], right ?

If my assumptions are not correct then please post a more complete example. (A small section of complete WORKING code, with some comments, would be ideal).

 

[Jinxer]

I guess that "i" in your pseudo code is the current insertion pointer for the ring buffer? Your buffer could easily overflow if "i=54", say, on entry into your code. (This could be the case after 6 insertions of 9 values.) Your loop just assumes the ring buffer is big enough, and will attempt to assign buffer[54] ... buffer[62] when the buffer is intended to only have locations buffer[0] ... buffer[55], right ?

If my assumptions are not correct then please post a more complete example. (A small section of complete WORKING code, with some comments, would be ideal).

thanks for replying. Actually this is a problem I was given on the topic “modular arithmetic”. Those two blocks of pseudo codes were all the details provided to me. My guess is similar to yours in the sense that I believe the second block of codes produce garbage because the buffer overflowed as well. But since as said the topic is on modular arithmetic , I am not sure how to link the answer (to the question of why the 9 bytes codes are producing garbage” to modular arithmetic.

 

[Cubist]

A small section of complete WORKING code, with some comments, would be ideal

I should have written "runnable" rather than "working". You'll get help much more quickly if we can reproduce your exact problem.

 

[Cubist]

thanks for replying. Actually this is a problem I was given on the topic “modular arithmetic”. Those two blocks of pseudo codes were all the details provided to me. My guess is similar to yours in the sense that I believe the second block of codes produce garbage because the buffer overflowed as well. But since as said the topic is on modular arithmetic , I am not sure how to link the answer (to the question of why the 9 bytes codes are producing garbage” to modular arithmetic.

OK, @Dr.Peterson post #2 gives a strong hint to the answer then.

NOTE You might need to look up what a "ring buffer" is, if you don't already know.

Basically the code contains a bug such that it will only work for insertion size x, where 56 mod x = 0. (The % symbol in the code performs modulo). So repeatedly inserting 8 is OK, but 9 is not. For more examples x=4 or 14 would also be OK, but 5, 11 etc would not. Can you see why this is the case? Consider what happens when the end of the buffer is reached.

The ring buffer code should really check for the end of buffer for every single insertion, then it could cope with any "x" insertion size (at the expense of the code being a bit more complicated and very slightly slower). The idea is that when the insertion point gets to buffer[55] the next value should be inserted at buffer[0].

 

[Jinxer]

OK, @Dr.Peterson post #2 gives a strong hint to the answer then.

NOTE You might need to look up what a "ring buffer" is, if you don't already know.

Basically the code contains a bug such that it will only work for insertion size x, where 56 mod x = 0. (The % symbol in the code performs modulo). So repeatedly inserting 8 is OK, but 9 is not. For more examples x=4 or 14 would also be OK, but 5, 11 etc would not. Can you see why this is the case? Consider what happens when the end of the buffer is reached.

The ring buffer code should really check for the end of buffer for every single insertion, then it could cope with any "x" insertion size (at the expense of the code being a bit more complicated and very slightly slower). The idea is that when the insertion point gets to buffer[55] the next value should be inserted at buffer[0].

Ah ok. Thank you so much. That was very helpful. I looked up ring buffer as well. It’s basically a circular buffer. But If that’s the case, I don’t understand why inserting 9 won’t work though. Since there won’t be a buffer overflow, the insertion point can be at like buffer[4] (for example) after it finishes a cycle. In the pseudo code above, why must it be mod x = 0 ? (8,4 or 14 etc I know they are multiples of 56) I am just trying to understand this last part, sorry.

 

[Dr.Peterson]

What you're doing here is simulating a ring buffer in a linear array! It must not overflow, but that isn't automatic; the code has to prevent that. This code doesn't.

Did you try following the details of Cubist's scenario?

Consider what happens when the end of the buffer is reached.

Look at your code:

But when I changed it to 9 bytes long

for j=0 to 8:
buffer[i+j] = newData[j]
i = (i+9) % 56

You have a 56-byte array, so if the index reaches 56 or more, you are writing into memory that is not reserved for this array. The first 6 entries will start at buffer[0], buffer[9], buffer[18], buffer[27], buffer[36], buffer[45], and the 7th will start at buffer[54]. But this will insert bytes at buffer[54], buffer[55], buffer[56], and you have just written over something else in memory! Then i will be set to (54+9) % 56 = 7 -- but nothing has been written into buffer[0] through buffer[6].

You need to learn to simulate code on paper to see what it does.

 

[Jinxer]

What you're doing here is simulating a ring buffer in a linear array! It must not overflow, but that isn't automatic; the code has to prevent that. This code doesn't.

Did you try following the details of Cubist's scenario?

Look at your code:

You have a 56-byte array, so if the index reaches 56 or more, you are writing into memory that is not reserved for this array. The first 6 entries will start at buffer[0], buffer[9], buffer[18], buffer[27], buffer[36], buffer[45], and the 7th will start at buffer[54]. But this will insert bytes at buffer[54], buffer[55], buffer[56], and you have just written over something else in memory! Then i will be set to (54+9) % 56 = 7 -- but nothing has been written into buffer[0] through buffer[6].

You need to learn to simulate code on paper to see what it does.

I did simulate the codes on paper. Which is why I was puzzled. Going by this logic, the first block of pseudo codes (the 8 bytes one that’s supposed to work) will overflow as well. Because at the 7th loop iteration/when j=6 , i will be set to (48+8)%56 = 0. which means the final 8th iteration / when j=7, it will be written into buffer[i+j=7]. Isn’t that an overflow as well?

 

[Dr.Peterson]

I did simulate the codes on paper. Which is why I was puzzled. Going by this logic, the first block of pseudo codes (the 8 bytes one that’s supposed to work) will overflow as well. Because at the 7th loop iteration/when j=6 , i will be set to (48+8)%56 = 0. which means the final 8th iteration / when j=7, it will be written into buffer[i+j=7]. Isn’t that an overflow as well?

I'm a little confused; you said initially "that works" (about the first program). Now you say it didn't. But it does! (I'm now wondering if that was what the problem itself said, not your own opinion. It might have helped if you had quoted the problem as given to you from the start, rather than making it look as if you wrote the code yourself, and understood it.)

But here is the code:

for j=0 to 7:
    buffer[i+j] = newData[j]
i = (i+8) % 56

Now, I'm presuming that i is an external variable that was initialized to 0, and also that your pseudocode means that the second line constitutes the loop controlled by the first line, and the third line is performed once, at the end of this "insert" routine, which is called each time you want to insert an item. (If not, then it's wrong.)

I think you're misinterpreting the code. The j loop is to copy the 8 bytes of one entry. After that, j is out of scope; it doesn't count the number of items inserted. The loop is not to insert 8 items, but to copy the 8 bytes of one item.

So on the 7th call to this routine, i will have been incremented 6 times, to 48; the loop moves 8 bytes, to buffer[48+00 to buffer[48+7]=buffer[55], the last byte in the buffer. Then it will be reset to 0, since it is changed from 48 to (48+8)%56 = 0. This sets it up for the 8th insertion, which will be at the start of the buffer. And that's right where it should go. (I have no idea why you say that writing to buffer[7] is overflow.)

 

[Cubist]

Jinxer, you're probably new to programming and the terminology. When the ring buffer insertion point goes from 55 back to 0 this is not called overflow. I don't think there is a specific word for this event. The old data at [0],[1], etc starts to be overwritten. This is expected behavior since the ring buffer is designed to store (up to) the last 56 values only. So you expect to overwrite (and loose) "old" data.

The word "overflow" that Dr.Peterson and I have used in this context means writing to an unallocated index in an array.
See if you can follow this pseudo code which might help to illustrate...

int a[3] // allocate an array that can store up to THREE integer values
a[0] = 7 // assign the value "9" to the first element of the array
a[1] = 8
a[2] = 9 // assign the value "7" to the LAST element of the array
a[0] = 10 // assign the value "10" to the first element of the array - overwriting the previous value - this is fine
a[5] = 11 // OVERFLOW - writing to any element that is beyond the length of 3 that was initially requested. See (*) below
a[-1] = 13 // UNDERFLOW - writing to an element that is before the start of the array

Both the last two commands might cause the program to crash because they try to access/ change memory locations that have not been allocated (reserved).

In the post#1 I would assume that "buffer" was allocated with length 56. The line " i = (i+8) % 56 " implies that this might be the case.


*- some computer languages will automatically make the array longer (certainly Matlab does). But most that I've come across don't tolerate overflow.