troubles with bitmap parsing

[austanss]

I've put together a dysfunctional bitmap parser that's confusing the **** out of me.
I have a proper bitmap but it keeps parsing incorrectly...

Code:

Code: Select all

static inline uint8_t get_bit(uint64_t source, uint8_t bit)
{
	return (source & ( 1 << bit )) >> bit;
}
. . .
void Terminal::put_entry_at(char c, uint8_t color, size_t x, size_t y)
{
	uint64_t font_selector = 0x1824427E42424200; // hardcoded (temp), 'A'

	uint8_t byts[64];

	for (uint8_t i = 1; i <= 64; i++)
	{
		byts[i] = get_bit(font_selector, i);
	}

	for (int i = 63; i >= 0; i--)
	{
		if ((i + 1) % 8 == 0)
			serial_msg('\n');
		serial_msg(byts[i] + 48); // 48, ASCII code '0'
	}
}

What the bitmap should look like:

Code: Select all

00011000
00100100
01000010
01111110
01000010
01000010
01000010
00000000

What I get from serial:

Code: Select all

00000000
00000000
00000000
00000000
,1000010
01000010
01000010
00000000

What I see consistently is the top half of the bitmap not being parsed/shown.

Anyone notice anything wrong here?

[Gigasoft]

Hint: What type is 1 << bit?

[austanss]

Hint: What type is 1 << bit?

Uhm, I'm pretty sure 1 is an integer by default... and bit is a unsigned char...

I don't get it...

[bzt]

Uhm, I'm pretty sure 1 is an integer by default... and bit is a unsigned char...
I don't get it...

Why don't you just do

Code: Select all

return (source >> bit) & 1;

? That's one less operation, so it's faster.

But if I were you, I would not use this highly inefficient code at all. There's a function call in the loop, which flushes the CPU instruction cache, not to mention that the compiler optimizer would assume many GPR may change. It's much more optimal to use:

Code: Select all

   for (uint64_t i = 0, mask = 1; i < 64; i++, mask <<=1)
   {
      byts[i] = (font_selector & mask) >> i;
   }

If you use "font_selector & mask" directly in a condition to determine the pixel's color, then there's no need for the ">> i" btw. The wiki page PC Screen Font has an example code like this. Using a mask also has the advantage that you can shift the mask bit both ways without performance penalty, so it works if the bitmap is coded in left-to-right (most significant bit encodes the pixel on the left). Btw that's the more common encoding.

Cheers,
bzt

[austanss]

Uhm, I'm pretty sure 1 is an integer by default... and bit is a unsigned char...
I don't get it...

Why don't you just do

Code: Select all

return (source >> bit) & 1;

? That's one less operation, so it's faster.

But if I were you, I would not use this highly inefficient code at all. There's a function call in the loop, which flushes the CPU instruction cache, not to mention that the compiler optimizer would assume many GPR may change. It's much more optimal to use:

Code: Select all

   for (uint64_t i = 0, mask = 1; i < 64; i++, mask <<=1)
   {
      byts[i] = (font_selector & mask) >> i;
   }

If you use "font_selector & mask" directly in a condition to determine the pixel's color, then there's no need for the ">> i" btw. The wiki page PC Screen Font has an example code like this. Using a mask also has the advantage that you can shift the mask bit both ways without performance penalty, so it works if the bitmap is coded in left-to-right (most significant bit encodes the pixel on the left). Btw that's the more common encoding.

Cheers,
bzt

The first bit you mentioned actually fixed it. Thanks!

[bzt]

I don't understand the mask code.

Which part? You use a variable that has exactly one bit set. Then in each iteration you shift that to the left or to the right. This way to determine if a particular bit is set in font_selector, you only need to do "font_selector & mask".

I don't have color in my text yet either so I don't have a use for that...

But you'll have to use a pixel to write to the screen. For now, you're using '0' and '1', but those going to be background pixel color and foreground pixel color. Something like:

Code: Select all

uint32_t bg = 0x000000 /* black */, fg = 0xFFFFFF /* white */;
...
byts_pixels[i] = font_selector & mask ? fg : bg;

So there's no need for the ">> i" part, you can even spare that operation too.

Cheers,
bzt

[alexfru]

Hint: What type is 1 << bit?

Uhm, I'm pretty sure 1 is an integer by default... and bit is a unsigned char...

I don't get it...

I'm going to give you some C++ reference links. C is almost identical here.

cpp ref: operator arithmetic:

Bitwise shift operators
...
The return type is the type of the left operand after integral promotions.

cpp ref: implicit conversion:

Integral promotion
...
In particular, arithmetic operators do not accept types smaller than int as arguments, and integral promotions are automatically applied after lvalue-to-rvalue conversion, if applicable.

cpp ref: integer literal:

Integer literal
...
The type of the literal
...
The type of the integer literal is the first type in which the value can fit, from the list of types which depends on which numeric base and which integer-suffix was used.
...
no suffix | decimal base

So, combining all of these together, 1 is int, the result of the shift of this 1 is int as well.

Now, how many bits are your ints (which, as we just determined, is the type of your "( 1 << bit )")? How many bits is uint64_t?

If you add the "ULL" suffix to your 1, that 1 will be an unsigned integer with at least 64 bits. It won't be truncated at/after position 31, which can give you undefined behavior:
cpp ref: operator arithmetic:

Bitwise shift operators
...
For signed and non-negative a, if a * 2**b is representable in the unsigned version of the return type, then that value, converted to signed, is the value of a << b (this makes it legal to create INT_MIN as 1<<31); otherwise the behavior is undefined.
...
In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.

C is slightly different here:
C2x N2478:

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has
an unsigned type, the value of the result is E1 × 2**E2, reduced modulo one more than the maximum
value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2**E2 is
representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

It's safer to be stricter as in C.

You need to learn the language better.