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

Go To Last Post
14 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

 

My first stab at it was this:

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?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

 

[edit] my number was wrong   val &= ~0x1ff

Last Edited: Fri. May 29, 2020 - 07:39 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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/...

#2 Hardware Problem? Read AVR042.

#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."

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

(Value + 511) & ~511

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes you are right!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

alank2 wrote:
David that is the simplest and most effective - well done sir! 

Didn't you ever do any rounding on paper or other?  Add half, then discard the lower digits.  [Whether to adjust the exact "half" like Brian did is left as an exercise for the reader]  Just like 123.45 rounded to the nearest [say] integer.  Only in your case the whole number to the left of the decimal is the desired power-of-two.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The issue was that my "go to" plan to divide the number to something smaller so the part I didn't want is removed and then multiplying it again to get it back to where it was without the truncated part.  It didn't really occur to me how "expensive" dividing was for a CPU back then, and I just hadn't thought of using & to do the same thing