Take the 2-minute tour ×

I'm working on a program that deals with a file that uses hashes. The data is divided into blocks length 0x1000. I need to calculate the amount of blocks a segment with a certain starting and ending offset covers.

For example, if the starting offset of the segment was 0x2000 and the ending was 0x3523, it would mean that it takes up two blocks, 0x2000 and 0x3000. It doesn't take up the full 0x2000 bytes in the data blocks, but it's considered to "take up a block" when it's inside it. My first thought was to do:

( ( EndingOffset - StartingOffset ) + 0xFFF ) >> 0xC

This is the equivalent of Math.Ceil((EndingOffset - StartingOffset) / 0x1000), but I'm new to bitwise operators and like the challenge of working with them.

Anyway, the logic was flawed, as, and this is the case that got me, if the starting offset is 0x3D8A and the end offset 0x671D, the difference between the two is 0x2993. Rounded up that's 0x3000, or three blocks. The segment actually takes up four, 0x3000, 0x4000, 0x5000, and 0x6000. So my next train, and unfortunately my last, was to instead find the difference between the the offset of the first block the segment is in, and the offset of the first block the segment isn't in.

With 0x3D8A and 0x671D, this brings me to (0x7000 - 0x3000) >> 0xC, which successfully yields the correct amount of blocks, 4. The way I wrote it is what I want to improve, which is:

BlockSize = ((((OffsetEnd + 0xFFF) >> 12) + 1) - ((OffsetStart + 0xFFF) >> 12));

I know I've over-complicated a simple problem, but I can't wrap my little brain around how to write it better.

edit: That's embarrassing. I don't know how I came to that instead of

(((OffsetEnd + 0xFFF) >> 12) - (OffsetStart >> 12));

Still doesn't seem complete though.

edit 2: Sorry, forgot to mention that the ending offset is exclusive, not inclusive and is the position after the last byte of the segment meaning:

(((OffsetEnd - 1 + 0xFFF) >> 12) - (OffsetStart >> 12));

edit 3: Going off of Kerek's answer, I end up with:

BlockSize = 1 + (offsetEnd - 1 >> 12) - (offsetStart >> 12);

..or, with counting from 0,

BlockSize = (offsetEnd - 1 >> 12) - (offsetStart >> 12);

edit 4: Forget the counting from zero, I'm sticking with:

share|improve this question
Is the end offset inclusive or exclusive? –  Kerrek SB Jan 4 '12 at 4:22
Exclusive. Sorry, should have clarified –  mowwwalker Jan 4 '12 at 4:25

2 Answers 2

up vote 0 down vote accepted

Assuming that your data ranges are given as [start, end), it's quite simple:

unsigned int start_block = start_offset / 0x1000;
unsigned int end_block = end_offset / 0x1000;

unsigned int number_of_blocks = end_block - start_block + (end_offset > start_offset && end_offset % 0x1000 > 0 ? 1 : 0);

The bitfiddling equivalent of / 0x1000 is >> 12, I suppose.

Your data will occupy the block range [start_block, end_block). Note that block 0 is [0x0000, 0x1000), block 1 is [0x1000, 0x2000)`, etc.

As @Ron pointed out, you'll need one conditional to distinguish whether the last ("one-past") block is empty or not, and increment the block count by one in the latter case.

share|improve this answer
That was my initial logic, but 0x3D8A would become 3, 0x671D would become 6, and the number would become 3, when it's meant to be 4. –  mowwwalker Jan 4 '12 at 4:26
@Walkerneo: No, it's meant to be 3, since numbering starts at zero! –  Kerrek SB Jan 4 '12 at 4:28
Nevermind, you're right. No clue why this didn't occur to me. –  mowwwalker Jan 4 '12 at 4:31
I would amend this to add one to number_of_blocks as a count of blocks should not be zero based (as opposed to the last block index which should). –  Ron Warholic Jan 4 '12 at 4:31
@KerrekSB: Yes however if you use one block you need to differentiate between one and zero blocks returned anyways. For example, if you have 0x3000 and 0x3FFF as start and end you'll get number_of_blocks = 0. How do you distinguish that from having no data without a conditional? –  Ron Warholic Jan 4 '12 at 4:42

( ( EndingOffset - StartingOffset ) + 0xFFF ) >> 0xC + (StartingOffset & ~(0xFFF) != 0)

This would have the succinct beginning you have and it will see if StartingOffset falls on a block boundary or not. If it doesn't, add 1.

share|improve this answer
That seems more complicated... –  mowwwalker Jan 4 '12 at 4:29

Your Answer


