Logical Question

[electroRF]

Hi,
I got a nice question which is also related to the other topic on Circular Buffer, and I'd love hearing your ideas on it

You got a 8KB buffer which you logically divide into 2 equally-sized parts, A [0-4KB), B [4KB-8KB).

You start running circularly on that buffer, each time writing few bytes into it (different amount each time, but not more than few hundreds of bytes).

How would you spot the moment in which you moved from one section to the other?

e.g. you were @ address (&Buff[0] + 4090), which is in Section A, now you wrote 10 bytes, therefore you moved to Section B @ address (&Buff[0] + 4100).

How would you tell at the end of that writing, that you're now in a different Section then you were before? (e.g. you're now at section B, while you were at section A).

The obvious way would be:

char section = 'A'; //Global pointer, initialized to 'A', since we start writing the buffer from the beginning, at section A.

//ptr is the running pointer. it can be assumed it's always within the Buffer's range
if ( (ptr < &Buff[0] + 4096) && (Section == 'B') )
{
    section = A;
    //Moved to a different section! do your thing here.
}
else if ( (ptr >= &Buff[0] + 4096) && (Section == 'A') )
{
    section = B;
    //Moved to a different section! do your thing here.
}

Would you do it in another way?

 

[NorthGuy]

Assume you use offset from the beginning of the buffer instead of absolute ptr (which is easier anyway):

if (offset&0x1000) {
  // we're in the top half
}

If you want to do DMAs in halfs and use the model we were discussing in the other thread:

int TopNext = 0; // marks if the next transfer should be the top
 
if (Head&0x1000^TopNext) {
  // we need to transfer something
  if (TopNext) {
    // transfer top
  } else {
    // transfer bottom
  }
  TopNext ^= 0x1000;
}

 

[electroRF]

Hi NorthGuy,
Thank you, that's a beautiful implementation!
I like it that it does not use any Compare, which saves Cycles, right? (you used XOR instead of Compare)

I think you can spare the if (TopNext) Branch, by using the TopNext as a parameter for the DMA Triggering function.
i.e., you'd provide the DMA Trigger Function, with source Address &SmallBuff[TopNext], Is it correct?

I'm thinking of dividing the Buffer into 4 equally-sized Buffers - Sections A [0-2KB), B [2KB-4KB), C [4-6KB), D [6KB-8KB).

1. How would recognize the moment in which you moved to another Section (1/4 Buffer), and from which Section you moved so you could tell the DMA to transfer that Section you moved from?
e.g. you were at address 4090 which is in Section B, and wrote 10Bytes, therefore moved to Address 4100 which is in Section C - therefore you moved from Section B to C, and you'd like tell the DMA to transfer Section B.

2. in the Example above, How would you tell if the DMA for example failed to transfer Section B, so the next time you moved a section, which would be moving from Section C to Section D, you'd tell the DMA to transfer Both Section B and C?

Thank you NorthGuy

 

[NorthGuy]

I think you can spare the if (TopNext) Branch, by using the TopNext as a parameter for the DMA Triggering function.
i.e., you'd provide the DMA Trigger Function, with source Address &SmallBuff[TopNext], Is it correct?

Good idea, quite right.

I'm thinking of dividing the Buffer into 4 equally-sized Buffers - Sections A [0-2KB), B [2KB-4KB), C [4-6KB), D [6KB-8KB).

1. How would recognize the moment in which you moved to another Section (1/4 Buffer), and from which Section you moved so you could tell the DMA to transfer that Section you moved from?
e.g. you were at address 4090 which is in Section B, and wrote 10Bytes, therefore moved to Address 4100 which is in Section C - therefore you moved from Section B to C, and you'd like tell the DMA to transfer Section B.

Same thing. Instead of TopNext you define WriteNext, which will now use 2 bits instead of one. And then to figure out if you need to write:

if ((Head&0x1800) != WriteNext)

To advance it to the next section you do:

WriteNext = (WriteNext+0x800)&0x1800;

or, if you maintain Tail at where you do DMA:

Tail += 0x800; // because you have just gave 0x800 bytes to DMA
WriteNext = Tail&0x1800; // do it here because it won't change until after next transfer

2. in the Example above, How would you tell if the DMA for example failed to transfer Section B, so the next time you moved a section, which would be moving from Section C to Section D, you'd tell the DMA to transfer Both Section B and C

What sort of failures do you have in mind?

 

[electroRF]

Hi NorthGuy,
Thank you very much

Awesome Implementation for the 4 blocks

Regarding the 2-Blocks Implementation, i.e. Double Buffer.

You actually converted the

if((ptr <&Buff[0]+4096)&&(Section =='B'))

that I wrote (which is actually composed of two ' if '), Into a more efficient ' if '

if(Head&0x1000^TopNext)

By using an offset instead of absolute address, and the fact which the buffer size is a power of 2.

I wonder, if the absolute address is used, and the buffer size is not a power of 2, e.g. 6KB, would you be able to make that ' if ' condition still composed of just one 'if' ? (and not two ' if ' as I did)
(that ' if ' should tell if the DMA needs to transfer the other 'half' block or not, and if yes, which half block to transfer)

 

[NorthGuy]

I wonder, if the absolute address is used, and the buffer size is not a power of 2, e.g. 6KB, would you be able to make that ' if ' condition still composed of just one 'if' ? (and not two ' if ' as I did)
(that ' if ' should tell if the DMA needs to transfer the other 'half' block or not, and if yes, which half block to transfer)

Of course not. Dividing by numbers which are power of 2 is very easy. Dividing by arbitrary numbers is very slow and inefficient. That's why when you try to make something fast, you align everything, make everything power of 2 etc.

When you try to save space, you pack everything and use awkward sizes. You save space, but the processing gets slow.

 

[electroRF]

Hi NorthGuy,

Thank you Again

I thought of the following code, which uses only one ' if '.

it uses absolute address and the Buffer Size does not need to be a power of 2.

It seems to be efficient.

What do you think?

UINT32 GlobalSign = 0x8000-0000; //Global Variable, initialized to negative;

Sign = (runningPtr - Mid_Address) & 0x8000-0000; //Mid_Address = Middle Address of Small Buffer
Disable_Interrupts;
if (Sign ^ GlobalSign) //Check if Sign bit Changed
{
    GlobalSign ^= 0x8000-0000;
    Enable_Interrupts;
    Trigger_DMA(Sign); //Sign value indicates which Half Block to transfer;
}
else
    Enable_Interrupts;

I put the ' if ' condition and GlobalSign update under Disabled-Interrupts Mode, to prevent a situation in which I could get Interrupted after I entered the IF but before the update of GlobalSign, and in thic case, I'd trigger the DMA twice.

Does that seem right to you?

 

[NorthGuy]

If by 0x8000-0000 you mean 0x80000000 then it'll work. It is, however, one more operation than the other one. Here you "subtract", "and" and "xor". The other one only had "and" and "xor".

Cannot comment on interrupt disabling because I don't know the whole scheme. I would assume if DMA is already active, you wouldn't trigger DMA and change the GlobalSign. Therefore, there's no need in disabling interrupts.

 

[electroRF]

Hi NorthGuy.
Thank you my friend

I indeed meant to 0x80000000. (just wanted to make it clearer for reading).

You're right, I perform 3 operations - Subtract, And, Xor.
I might not need the AND Operation, because the ALU already holds a Negativity bit which indicates if result was negative or non-negative.

Regarding Disabling Interrupts.

I don't know if the DMA is still active or not, until I enters that ' if ' condition which tells me that I passed to a different half buffer.

Once I'm inside that ' if ' condition, I do both - change the GlobalSign, and trigger the DMA.

If the DMA is active, I believe I'll have to handle it - try to trigger it again with the same inputs (same half buffer to transfer).

If I don't disable interrupts, I might change the Global Sign Twice, with just one 'border crossing' from one half buffer to another.

 

[NorthGuy]

I might not need the AND Operation, because the ALU already holds a Negativity bit which indicates if result was negative or non-negative.

But you also need the result of the "and" operation to do "xor". If you avoid the "and", you will need to check the "sign" processor's flag after you do "xor". Actually you can do that, but you would have to do this in assembler.

I don't know if the DMA is still active or not, until I enters that ' if ' condition which tells me that I passed to a different half buffer.

Once I'm inside that ' if ' condition, I do both - change the GlobalSign, and trigger the DMA.

If the DMA is active, I believe I'll have to handle it - try to trigger it again with the same inputs (same half buffer to transfer).

If I don't disable interrupts, I might change the Global Sign Twice, with just one 'border crossing' from one half buffer to another.

You do not need to disable interrupts before you check the condition. Disabling and enabling interrupts for every check is a huge performance hit. Instead, you enter the "if", then you

- disable interrupts
- check if DMA is finished with previous assignment
- if DMA is done, you trigger the new DMA and adjust the pointers
- if DMA is still busy, you do nothing.
- enable interrupts

 

[electroRF]

Hi NorthGuy,
Thank you as always

You do not need to disable interrupts before you check the condition. Disabling and enabling interrupts for every check is a huge performance hit. Instead, you enter the "if", then you

- disable interrupts
- check if DMA is finished with previous assignment
- if DMA is done, you trigger the new DMA and adjust the pointers
- if DMA is still busy, you do nothing.
- enable interrupts

I've been contemplating your method.

Say that the uC finished writing the bottom 1/2 Small Buffer, and the uC is now writing the top 1/2 Small Buffer.
Therefore, I'd trigger the DMA to transfer the bottom 1/2 Small Buffer.
However, if the DMA is still busy for some reason with transferring the top 1/2 Small buffer (it should not happen, but perhaps due to some temporary delay),
Would I need to stop it and tell it to give up the top 1/2 Small Buffer and start moving the Bottom 1/2 Small Buffer?

Otherwise, if I do nothing, the DMA and the uC would remain 'out of sync'.

 

[NorthGuy]

If you use the same Head and Tail for both DMA and buffer, DMA will never gets out of sink. If you write too fast, some of the transfers may be lost or corrupt, but the only way to fight this is to have a larger buffer. We don't really know how large a buffer is needed because you keep all the timing information secret.

If everything is timed correctly, you should never get into a situation where you want to start transferring bottom while DMA is still transferring top. That would mean that you overwrote the part of the buffer that DMA is transferring.

The reason for checking if DMA is busy is to account for a situation when some other thread interrupted you and already started the DMA.