В современной компьютерной графике, а так же при разработке быстрых алгоритмов ориентированных на использование большого числа данных, часто требуется упаковать вещественные числа в целые, т.е. использовать числа с фиксированной точкой.
Это дает преимущества:
- При запаковке можно получить значительно меньший расход памяти (для хранения или передачи по сети).
Недостатки:
- Необходимо конвертировать данные при запаковке и распаковке. Поэтому имеет смысл использовать это только тогда, когда вся логика будет вестись только с такими числами.
Однако, при не правильной запаковке, можно получить значительную потерю точности из-за которой придется отказаться от данной техники. Данная статья расскажет вам методы запаковки данных и покажет методы, которых стоит избегать.
В статье будут представлены конкретные задачи и методы их решения, с объяснением некоторых деталей. Предполагается, что пользователь владеет знаниями программирования и пониманием того, как разные типы данных хранятся в памяти.
Некоторые определения
В статье все типы переменных имеют конкретный размер, поэтому название типа переменной будет указывать тип (i - int, u - unsigned int, f - floating point value), а цифрой будет указано количество бит, отведенных под значение данного типа. Например u8, u16, u32, u64, i8, i16, i32, i64, f32, f64.
Так можно определить данные типы:
1
2
3
4
5
6
7
8
9
10
typedef unsigned char u8;
typedef signed char i8;
typedef unsigned short u16;
typedef signed short i16;
typedef unsigned int u32;
typedef signed int i32;
typedef unsigned long long u64;
typedef signed long long i64;
typedef float f32;
typedef double f64;
Число с фиксированной точкой - это формат представления вещественного числа, при котором значение в памяти хранится как целое.
Число с плавающей точкой - это формат представления вещественного числа, при котором значение в памяти представлены в виде мантиссы и показателя степени.
Некоторые сведения о типе float в С++:
float - 32 битный тип хранения вещественного числа, утвержденный в стандарте IEEE 754. Именно с этим типом данных и будет вестись работа в данной статье. f32 число имеет 23 бита мантиссы, 8 бит показателя степени двойки и один бит - знаковый. Т.е. число будет равно:
1
value = (-1)^s * m * 2^e // m - мантисса, e - показатель степени, s - знак
Если мы захотим преобразовать это число в число с фиксированной точкой, то можно зафиксировать показатель степени и работать только с мантиссой, как с целым числом. Потом при желании можно будет восстановить изначальное значение вещественного числа.
Получение чисел с фиксированной точкой:
Простейший вариант получения числа с фиксированной точкой:
1
2
3
f32 value;
u32 fixValue = u32( value * V ); - получение числа с фиксированной точкой.
f32 newValue = fixValue / V; - восстановление вещественного числа
Где V - может быть любым, но если оно будет равно степени двойки, то не будет теряться точность мантиссы при преобразовании. Если V будет равно 2 ^ 23, то будет использоваться вся мантисса в чистом виде. Однако часто идет запаковка данных в тип меньшего размера, например u16, для чего используются меньшие величины делителя.
Напишем базовые функции запаковки и распаковки чисел из формата с плавающей в формат с фиксированной точкой. Конечно нужно написать функции для всех типов запаковки, но здесь будут представлены только две. Остальные аналогичны:
1
2
3
4
5
6
7
8
9
10
11
u32 Pack( f32 val, u8 bitOffset )
{
return u32( val * ( 1 << bitsOffset ) );
//return i32( val * ( 1 << bitsOffset ) ); - эти варианты так же возможны, в зависимости от цели
//return u16( val * ( 1 << bitsOffset ) );
//return i16( val * ( 1 << bitsOffset ) );
}
f32 Unpack( u32 val, u8 bitOffset )
{
return (f32)val * ( 1 << bitsOffset );
}
Выбор формата упаковки:
Выбор формата упаковки, определяется двумя вещами: какие по размеру значения нужно хранить и сколько отводится памяти для их хранения. Форматы с фиксированной точкой в этой статье будут записываться в виде пары числе (x.y), где x - количество бит, отводимое для целой части, а y - для дробной части числа. Вот наиболее часто используемые форматы запаковки:
1
2
3
4
5
6
7
8
9
10
f32->u8: (0.8) - это позволяет хранить числа в диапазоне [0..1). Но 1 - не представимое в данном виде. Точность такого числа будет равна 1/256.
f32->u16: (0.16) - позволяет с большой точностью хранить числа в диапазоне [0..1). Но 1 - не представимое в данном виде. Точность такого числа будет равна 1/65536.
f32->u16: (1.15) - точность такого числа ниже чем в предыдущем варианте, однако можно точно представить число 1.
f32->u16: (6.10) - позволяет хранить числа в диапазоне [0..64) с достаточно высокой точностью. Число 64 не представимое в данном виде. Удобно в таком формате хранить не очень большие числа, например размеры частиц или объектов.
f32->u16: (7.9) - для диапазона [0..128). Это подойдет, если нужно точно представлять число 64.
f32->u16: (10.6) - для диапазона [0..1024). Точность такого числа не высока - 1/64, однако
f32->u16: (12.4) - для диапазона [0..4096). Точность такого числа не высока - 1/16, однако этот вариант хорошо подходит например для кодирования экранных координат. Этот вариант подходит для всех возможных разрешений, а точность меньше пикселя практически не важна.
vec3 -> short4 - вариант, когда вектор (три числа f32) нужно закодировать в виде 4-х чисел u16. Такая структура будет занимать 8 байт, вместо 12.
vec3 -> ubyte4 - вариант, когда вектор нужно закодировать в виде 4-х чисел u8. Такая структура будет занимать 4 байта, вместо 12.
Операции с числами с фиксированной точкой:
Задача 1
Запаковать число f32 в i32 без потери точности. Поскольку мантисса хранится в 23 битах, то максимально точным будет формат с фиксированной точкой (9.23). Видим, что для целой части числа остается только 9 бит. Это значит, что можно будет в таком виде хранить числа в диапазоне [0..512).
1
2
3
4
f32 src;
u32 pack = Pack( src, 23 ); // запаковка
...
f32 unpack = Unpack( pack, 23 ); // распаковка
Задача 2
Необходимо запаковать переменную типа f32 src которая содержит значение от 0 до 1 в однобайтовое целое число u8 от 0 до 255. Это иногда необходимо при конвертировании цвета из одного формата в другой. Необходимо проделать данную операцию с наименьшей потерей точности.
Решение:
1
u8 dest = u8( src * 255.0f + 0.5f ); (1)
По стандарту С++ приведение вещественного числа к u8 приведет к отбрасыванию дробной части. Чтобы округлить значение до ближайшего целого числа необходимо еще добавить 0.5f.
Задача 3
Требуется преобразовать f32 src в число с фиксированной запятой u16 и восстановить исходное значение.
Решение:
1
2
3
u16 dest = u16( src * ( 1 << 15 ) ); (2)
u16 dest = u16( src * ( 1 << 16 ) ); (3)
u16 dest = u16( src * ( (1 << 16) - 1 ) ); (4) плохо
В случае (2), 15 бит мантиссы будут записаны в переменную. Значение будет от 0 до 32768, причем единица будет точно представима в таком виде. Данное число будет достаточно точным, потому что биты мантиссы сохранятся неизменными. В случае (3) значение будет от 0 до 65535 (т.е. точность будет выше чем в первом случае) но единица не будет иметь представления (т.е. при src == 1.0f будет переполнение). В случае (4) число будет так же от 0 до 65535 и единица будет нормально представима в данном виде, но будет потеря точности, т.к. в переменную будут записаны не биты мантиссы в чистом виде а после преобразования.
Для того чтобы восстановить исходное число нужно:
1
2
f32 newSrc = dest / ( 1 << 15 ); для (2)
f32 newSrc = dest / ( 1 << 16 ); для (3)