## Best way to round up a value to a block/page size...

14 posts / 0 new
Author
Message

I've been writing a small FAT-8 type filesystem for something and one of the things I need to do is round a size up to a cluster size for example.  Say a cluster size of 512, it would take numbers like:

0 --> 0

1 --> 512

2 --> 512

511 --> 512

512 --> 512

513 --> 1024

```AFileSize=((AFileSize+(MF_sigstr.clustersize-1))/MF_sigstr.clustersize)*MF_sigstr.clustersize;
```

But this produced a call to a division function (it does not know that the clustersize is always a power of 2)

Then I tried:

```    if (AFileSize & (MF_sigstr.clustersize-1))
AFileSize+=MF_sigstr.clustersize;
AFileSize&=~(MF_sigstr.clustersize-1);
```

Which avoids the division successfully.

I wonder how others do this?  Is there a better way?

I think your numbers are wrong.
Val &0x1ff rounds to the lowest

 my number was wrong   val &= ~0x1ff

Last Edited: Fri. May 29, 2020 - 07:39 AM

Hmmm, without getting to the bottom of my first cup of coffee...

```uint16_t value;

if (value) {
value = (--value & 511) | 512
}```

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

(Value + 511) & ~511

David that is the simplest and most effective - well done sir!  What is funny is that I've been accomplishing it by trying bit shift right and then bit shift left again using division/multiplication for years!

```AFileSize = (AFileSize + MF_sigstr.clustersize-1) & ~(MF_sigstr.clustersize-1);
a1a:	40 91 06 01 	lds	r20, 0x0106	; 0x800106 <__data_end+0x2>
a1e:	50 91 07 01 	lds	r21, 0x0107	; 0x800107 <__data_end+0x3>
a22:	ca 01       	movw	r24, r20
a24:	a0 e0       	ldi	r26, 0x00	; 0
a26:	b0 e0       	ldi	r27, 0x00	; 0
a28:	01 97       	sbiw	r24, 0x01	; 1
a2a:	a1 09       	sbc	r26, r1
a2c:	b1 09       	sbc	r27, r1
a2e:	c8 0e       	add	r12, r24
a30:	d9 1e       	adc	r13, r25
a32:	ea 1e       	adc	r14, r26
a34:	fb 1e       	adc	r15, r27
```

Thanks everyone!

You often do this sort of operation e.g. for padding a bitmap

Likewise,  you round down with (Value) & ~511

You can calculate a mask value by ((1 << bits) - 1)

But you have to be careful with the width of a long expression e.g. (Value + 511) & ~511uL

Jest keep statements simple.   The Compiler will do a pretty good job.

David.

So, while I'm asking, is there a better way to do a bitmap bit setting/testing/clearing than this:

```#define CLEAR_BITMAP(x,y)              memset(x,0,y);
#define TEST_BITMAP_BIT(x,y)           ( x[y/8] & _BV(y%8) )
#define SET_BITMAP_BIT(x,y)            x[y/8] |= (uint8_t)_BV(y%8)
#define CLEAR_BITMAP_BIT(x,y)          x[y/8] &= (uint8_t)~_BV(y%8)
```

I could be more consistent by making the CLEAR_BITMAP also divide y by 8.  The TEST_BITMAP_BIT produces much more assembly than I expected, but I don't know how/if it can be improved.

Maybe a lookup table for the 8 _BV values?  I can try that and see what it yields.

Those macros are not how I would write them.   But GCC is pretty clever.   I suspect it will do a reasonable job.

For example,  /8 instead of >>3 probably uses shifts.

And %8 instead of &7 probably uses AND

I suspect that you have a pretty good understanding of ASM opcodes.

In which case you can inspect the LSS and make your own conclusions.

If in doubt,  look at proven code for KS0108 or SSD1306.   See how legacy code does it.    Remember that AVR-GCC was "not very good" when it first came out.    So the authors would have "helped" the Compiler as much as possible.

Current GCC is excellent.    You can write straightforward statements and expect the Compiler to create the best code.

David.

Last Edited: Sat. May 30, 2020 - 04:56 PM

I need to embrace the logical AND operation!

ironically when I changed it from %8 to &7, it compiled to 40 bytes more flash (2916 vs 2876)!

Last Edited: Sat. May 30, 2020 - 05:48 PM

No,  you want the BITWISE AND operation &

The logical AND is &&

I have not tried your macros.    I would not be surprised if they generate efficient code.

David.

Yes you are right!

Using:

const __flash uint8_t bitvalues[8]={1,2,4,8,16,32,64,128};

instead of _BV(x) dropped flash to 2660, and it is 2660 whether I used %8 or &7.