BitMap class limited to XY size 46340x46340

[belzecue]

Godot version:
3.3.stable

OS/device including version:
Linux Ubuntu 20.04.2, NUC7PY, 16 gigs ram.

Issue description:
Cannot create a BitMap larger than 46340 x 46340. Attempting to create a BitMap of (46341, 46341) crashes.

I wanted to use BitMap to create a 3D maze map index of blocks, so that I could build it fast logically before creating the mesh blocks. Since BitMap is 2D, I extended it to stack XY "frames" vertically, representing the Z dimension. e.g a 3D bitmap size of 2,3,4 would create a 2D BitMap of dimensions 2,12 with Y representing the four Z slots. Reading and writing gets translated from the 3D coords to the 2D bitmap coords. See below (in this example, the very first bit at 0,0 shown set to true):

2:-- 
1:-- 
0:-- Frame 3
2:-- 
1:-- 
0:-- Frame 2
2:-- 
1:-- 
0:-- Frame 1
2:-- 
1:-- 
0:X- Frame 0

This works well, except I quickly hit the dimension limit for BitMaps, which I was not expecting. I'm guessing the BitMap class is intended mainly for handling bitmap textures/images and therefore was never designed to handle anything larger than the typical 1K, 2K, 4K, 8K standards -- or in this case, 46K.

I'm mainly interested in understanding why the XY size limit is exactly 46340, which is a bit of a strange number in a world where we expect limits to be near power of twos. Thanks!

Steps to reproduce:
Attach below script to a node and run.

Minimal reproduction project:

extends Node


func _ready():
	test(46340)
	print("Repeating with dimension of 46341 (will crash in 3 seconds)...")
	yield(get_tree().create_timer(3),"timeout")
	test(46341)
	print("You'll never see this!")


func test(size: int) -> void:
	var bm: BitMap = BitMap.new()
	print("using max xy dimensions of %s..." % size)
	bm.create(Vector2(size, size))
	print(bm.get_size())
	bm.set_bit(Vector2(0, size - 1), true)
	print(bm.get_bit(Vector2(0, size - 1)))
	bm.set_bit(Vector2(size - 1, size - 1), true)
	print(bm.get_bit(Vector2(size - 1, size - 1)))
	
	

[Calinou]

I'm mainly interested in understanding why the XY size limit is exactly 46340, which is a bit of a strange number in a world where we expect limits to be near power of twos.

That explains it:

46,340 × 46,340 = 2,147,395,600
2^31 - 1 (signed 32-bit integer limit) = 2,147,483,647
46,341 × 46,341 = 2,147,488,281 > 2,147,483,647

[belzecue]

Ah, there it is. Nothing out of the ordinary. Thank you!

[akien-mga]

Well if it's going to crash, set_bit should throw an error (at least in debug builds) if the size is bigger than what it can encode.

[Xrayez]

I think this will also be a perfect time for someone to write a new test suite for BitMap as listed in #43440, maybe @resul4e would also be interested in fixing this issue as well.

[Xrayez]

godot/scene/resources/bit_map.h

Lines 42 to 44 in eb57dcd

	Vector<uint8_t> bitmask;
	int width = 0;
	int height = 0;

Maybe changing int to uint32_t could alleviate this limitation.

[resul4e]

godot/scene/resources/bit_map.h

Lines 42 to 44 in eb57dcd

	Vector<uint8_t> bitmask;
	int width = 0;
	int height = 0;

Maybe changing int to uint32_t could alleviate this limitation.

I don't think this is the problem, as width and height would still be more than inside their limits. I think something is going wrong in the Vector::resize() method. And we are not checking the Error it returns. I could change the BitMap::create() method so that it checks the Error the Vector::resize() returns and does not update the width and height if it returns an error.

[Xrayez]

I confirm that I've had issues with resizing Vector past some limit which would also crash Godot, in a similar class I've implemented in Goost called VariantMap. So, I don't exclude the possibility that the issue can be two-fold in this case.

[resul4e]

Well if it's going to crash, set_bit should throw an error (at least in debug builds) if the size is bigger than what it can encode.

BitMap::set_bit() normally does throw an error, but because we have set the width and height to their new values it happily tries to index into an array that has not been correctly set up.

[resul4e]

For now, I'll add a check in the create() method to see if the Vector is correctly initialized. If it fails to do this, we will not update the width and height. Unfortunately, this will not fix the issue @belzecue is having. However, I feel that modifying BitMap (and potentially Vector) to be able to handle larger arrays is outside of the scope of the changes I am currently making.

[belzecue]

I'm fine with sticking to the limit of 1290x1290x1290 for the purposes of my BitMap3D extended class, which I would round down to 1024x1024x1024 max just for simplicity. I'm working with 1m cubes, so that's a 1km volume, which is good enough. I can build arrays of these if need be.

If somebody had the urge to create a native Godot BitMap3D class, that would be pretty sweet too for all the voxellers out there :)

Thanks for adding the out-of-bounds size check.

[Xrayez]

For reference, CowData class uses int,

godot/core/templates/cowdata.h

Line 259 in bb6ece1

Error CowData<T>::resize(int p_size) {

But _get_size() returns uint32_t:

godot/core/templates/cowdata.h

Lines 132 to 139 in bb6ece1

	_FORCE_INLINE_ int size() const {
	uint32_t *size = (uint32_t *)_get_size();
	if (size) {
	return *size;
	} else {
	return 0;
	}
	}

This is either by design or a bug, at least it looks like to me. 😛

[mmahkamov]

The issue is caused by the bug in BitMap::create where the multiplication of two 32-bit integers, width and height, just overflows:

bitmask.resize(((width * height) / 8) + 1);

The solution is to cast width/height to uint64_t.

There are other issues:

1. width, height and vector size are declared as int. If there's no case where they can be set to -1, I'd suggest declaring them as size_t.
2. the result of the bitmask.resize call is not checked. The following memset() call may crash with NPE or overwrite memory.

[resul4e]

Yep, that's what I also found. I've fixed it on my machine and once I create the BitMap unit test PR, it should get fixed.

[resul4e]

However, I don't agree that casting to uint64_t in BitMap::create will fix it. We would have to rewrite the entirety of BitMap to use uint64's.

[belzecue]

Perhaps another reason to give BitMap a rewrite: issue #48545, where it consumes double the needed memory, cancelling one benefit of using an efficient bitmap.

[mmahkamov]

However, I don't agree that casting to uint64_t in BitMap::create will fix it. We would have to rewrite the entirety of BitMap to use uint64's.

1. Casting will fix the issue with allocation only, it's just a workaround.

2. For BitMap to work properly it needs to be rewritten to use uint64_t, you're right.

The reason being is that the bitmap size is defined using Vector2. The bit coordinates are also defined using Vector2. Vector2 uses double to store its members, so it's definitely larger than int used in BitMap.

While at it, I'd also change Vector<uint8_t> to Vector<size_t>, as it should be faster to access & manipulate 32-bit integers on some platforms.

3. Vector should be fixed to use size_t instead of int
4. CowData should be fixed to use size_t instead of uint32_t

[Calinou]

3. Vector should be fixed to use size_t instead of int
4. CowData should be fixed to use size_t instead of uint32_t

This is waiting on #21922 to be merged.

[mmahkamov]

bm.set_bit(Vector2(0, size - 1), true)
bm.get_bit(Vector2(0, size - 1))

How often these methods are called in a typical game? Would they benefit from overloaded methods which accept the bit positions as two doubles instead of Vector2, which avoids object construction?

[Calinou]

Would they benefit from overloaded methods which accept the bit positions as two doubles instead of Vector2, which avoids object construction?

The 3.x branch doesn't allow exposing overloaded methods. You have to expose separate methods such as set_bit and set_bitv (similar to Image's set_pixel and set_pixelv).

However, to keep compatibility with existing project, you can't rename the current set_bit to set_bitv, so you'd have to add something like set_bit_individual instead.

[akien-mga]

It seems to be a duplicate of #46842? We can keep this issue opened to see if anything specific can be done in BitMap to prevent a crash, but otherwise it's a core issue that needs to be solved in CowData.

[akien-mga]

This isn't fixed yet by #86730, but it becomes fixable. The BitMap code should be changed to use int64_t instead of int where relevant, which is now possible thanks to the changes in CowData.

Here's an up-to-date MRP: BitMap64bit.zip

Note that it doesn't crash, but triggers errors. It seems we added some guards in the past to prevent passing sizes bigger than INT32_MAX, that would have to be removed together with porting the class to support int64_t dimensions.