[webkit-dev] Proposal for serializing alpha channel values; request for algorithm help
Gavin Barraclough
barraclough at apple.com
Tue Nov 3 22:29:52 PST 2015
I’m too addicted to this.
I tested a few variants of BCD conversion, and based on some quick benchmarking on my machine it appears any would be a 40X – 50X improvement compared to an equivalent sprintf(_, “%f”, x/255.0).
The following chart shows the speedup, table size required to hold the BCD, and resulting string lengths for a few different policies.
Precision
Speedup vs
sprintf
Table Size
String Length,
Min
String Length,
Average
String Length,
Max
default,
with trailing zeros
~50X
768 bytes
8
8
8
default,
no trailing zeros
~40X
768 bytes
1
7.8
8
±1% tolerance
~40X
768 bytes
1
6.1
7
±5% tolerance
~45X
512 bytes
1
5.5
6
minimal
~45X
512 bytes
1
4.5
5
The first configuration matches printf default precision.
The second maintains the same accuracy but strips trailing zeros.
The third ensures accuracy within ±1% of the granularity of the step between values – so 1 converts to 0.003922 ±0.00003922, and 2 converts to 0.007843 ±0.00003922, etc.
The fourth is similar, with slightly looser tolerance.
The fifth is the minimal precision required for values to round trip.
Code for default precision with no trailing zeros below.
cheers,
G.
void unsignedCharToFloatString(unsigned char uc, char* out)
{
const unsigned char* data = unsignedCharToFloatData[uc];
*out++ = uc == 255 ? '1' : '0';
*out++ = '.';
*out++ = '0' + (data[0] >> 4);
*out++ = '0' + (data[0] & 0xF);
*out++ = '0' + (data[1] >> 4);
*out++ = '0' + (data[1] & 0xF);
*out++ = '0' + (data[2] >> 4);
*out++ = '0' + (data[2] & 0xF);
// Remove trailing zeros.
while (out[-1] == '0')
--out;
if (out[-1] == '.')
--out;
*out = '\0';
}
static const unsigned char unsignedCharToFloatData[256][3] = {
{ 0x00, 0x00, 0x00 },
{ 0x00, 0x39, 0x22 },
{ 0x00, 0x78, 0x43 },
{ 0x01, 0x17, 0x65 },
{ 0x01, 0x56, 0x86 },
{ 0x01, 0x96, 0x08 },
{ 0x02, 0x35, 0x29 },
{ 0x02, 0x74, 0x51 },
{ 0x03, 0x13, 0x73 },
{ 0x03, 0x52, 0x94 },
{ 0x03, 0x92, 0x16 },
{ 0x04, 0x31, 0x37 },
{ 0x04, 0x70, 0x59 },
{ 0x05, 0x09, 0x80 },
{ 0x05, 0x49, 0x02 },
{ 0x05, 0x88, 0x24 },
{ 0x06, 0x27, 0x45 },
{ 0x06, 0x66, 0x67 },
{ 0x07, 0x05, 0x88 },
{ 0x07, 0x45, 0x10 },
{ 0x07, 0x84, 0x31 },
{ 0x08, 0x23, 0x53 },
{ 0x08, 0x62, 0x75 },
{ 0x09, 0x01, 0x96 },
{ 0x09, 0x41, 0x18 },
{ 0x09, 0x80, 0x39 },
{ 0x10, 0x19, 0x61 },
{ 0x10, 0x58, 0x82 },
{ 0x10, 0x98, 0x04 },
{ 0x11, 0x37, 0x25 },
{ 0x11, 0x76, 0x47 },
{ 0x12, 0x15, 0x69 },
{ 0x12, 0x54, 0x90 },
{ 0x12, 0x94, 0x12 },
{ 0x13, 0x33, 0x33 },
{ 0x13, 0x72, 0x55 },
{ 0x14, 0x11, 0x76 },
{ 0x14, 0x50, 0x98 },
{ 0x14, 0x90, 0x20 },
{ 0x15, 0x29, 0x41 },
{ 0x15, 0x68, 0x63 },
{ 0x16, 0x07, 0x84 },
{ 0x16, 0x47, 0x06 },
{ 0x16, 0x86, 0x27 },
{ 0x17, 0x25, 0x49 },
{ 0x17, 0x64, 0x71 },
{ 0x18, 0x03, 0x92 },
{ 0x18, 0x43, 0x14 },
{ 0x18, 0x82, 0x35 },
{ 0x19, 0x21, 0x57 },
{ 0x19, 0x60, 0x78 },
{ 0x20, 0x00, 0x00 },
{ 0x20, 0x39, 0x22 },
{ 0x20, 0x78, 0x43 },
{ 0x21, 0x17, 0x65 },
{ 0x21, 0x56, 0x86 },
{ 0x21, 0x96, 0x08 },
{ 0x22, 0x35, 0x29 },
{ 0x22, 0x74, 0x51 },
{ 0x23, 0x13, 0x73 },
{ 0x23, 0x52, 0x94 },
{ 0x23, 0x92, 0x16 },
{ 0x24, 0x31, 0x37 },
{ 0x24, 0x70, 0x59 },
{ 0x25, 0x09, 0x80 },
{ 0x25, 0x49, 0x02 },
{ 0x25, 0x88, 0x24 },
{ 0x26, 0x27, 0x45 },
{ 0x26, 0x66, 0x67 },
{ 0x27, 0x05, 0x88 },
{ 0x27, 0x45, 0x10 },
{ 0x27, 0x84, 0x31 },
{ 0x28, 0x23, 0x53 },
{ 0x28, 0x62, 0x75 },
{ 0x29, 0x01, 0x96 },
{ 0x29, 0x41, 0x18 },
{ 0x29, 0x80, 0x39 },
{ 0x30, 0x19, 0x61 },
{ 0x30, 0x58, 0x82 },
{ 0x30, 0x98, 0x04 },
{ 0x31, 0x37, 0x25 },
{ 0x31, 0x76, 0x47 },
{ 0x32, 0x15, 0x69 },
{ 0x32, 0x54, 0x90 },
{ 0x32, 0x94, 0x12 },
{ 0x33, 0x33, 0x33 },
{ 0x33, 0x72, 0x55 },
{ 0x34, 0x11, 0x76 },
{ 0x34, 0x50, 0x98 },
{ 0x34, 0x90, 0x20 },
{ 0x35, 0x29, 0x41 },
{ 0x35, 0x68, 0x63 },
{ 0x36, 0x07, 0x84 },
{ 0x36, 0x47, 0x06 },
{ 0x36, 0x86, 0x27 },
{ 0x37, 0x25, 0x49 },
{ 0x37, 0x64, 0x71 },
{ 0x38, 0x03, 0x92 },
{ 0x38, 0x43, 0x14 },
{ 0x38, 0x82, 0x35 },
{ 0x39, 0x21, 0x57 },
{ 0x39, 0x60, 0x78 },
{ 0x40, 0x00, 0x00 },
{ 0x40, 0x39, 0x22 },
{ 0x40, 0x78, 0x43 },
{ 0x41, 0x17, 0x65 },
{ 0x41, 0x56, 0x86 },
{ 0x41, 0x96, 0x08 },
{ 0x42, 0x35, 0x29 },
{ 0x42, 0x74, 0x51 },
{ 0x43, 0x13, 0x73 },
{ 0x43, 0x52, 0x94 },
{ 0x43, 0x92, 0x16 },
{ 0x44, 0x31, 0x37 },
{ 0x44, 0x70, 0x59 },
{ 0x45, 0x09, 0x80 },
{ 0x45, 0x49, 0x02 },
{ 0x45, 0x88, 0x24 },
{ 0x46, 0x27, 0x45 },
{ 0x46, 0x66, 0x67 },
{ 0x47, 0x05, 0x88 },
{ 0x47, 0x45, 0x10 },
{ 0x47, 0x84, 0x31 },
{ 0x48, 0x23, 0x53 },
{ 0x48, 0x62, 0x75 },
{ 0x49, 0x01, 0x96 },
{ 0x49, 0x41, 0x18 },
{ 0x49, 0x80, 0x39 },
{ 0x50, 0x19, 0x61 },
{ 0x50, 0x58, 0x82 },
{ 0x50, 0x98, 0x04 },
{ 0x51, 0x37, 0x25 },
{ 0x51, 0x76, 0x47 },
{ 0x52, 0x15, 0x69 },
{ 0x52, 0x54, 0x90 },
{ 0x52, 0x94, 0x12 },
{ 0x53, 0x33, 0x33 },
{ 0x53, 0x72, 0x55 },
{ 0x54, 0x11, 0x76 },
{ 0x54, 0x50, 0x98 },
{ 0x54, 0x90, 0x20 },
{ 0x55, 0x29, 0x41 },
{ 0x55, 0x68, 0x63 },
{ 0x56, 0x07, 0x84 },
{ 0x56, 0x47, 0x06 },
{ 0x56, 0x86, 0x27 },
{ 0x57, 0x25, 0x49 },
{ 0x57, 0x64, 0x71 },
{ 0x58, 0x03, 0x92 },
{ 0x58, 0x43, 0x14 },
{ 0x58, 0x82, 0x35 },
{ 0x59, 0x21, 0x57 },
{ 0x59, 0x60, 0x78 },
{ 0x60, 0x00, 0x00 },
{ 0x60, 0x39, 0x22 },
{ 0x60, 0x78, 0x43 },
{ 0x61, 0x17, 0x65 },
{ 0x61, 0x56, 0x86 },
{ 0x61, 0x96, 0x08 },
{ 0x62, 0x35, 0x29 },
{ 0x62, 0x74, 0x51 },
{ 0x63, 0x13, 0x73 },
{ 0x63, 0x52, 0x94 },
{ 0x63, 0x92, 0x16 },
{ 0x64, 0x31, 0x37 },
{ 0x64, 0x70, 0x59 },
{ 0x65, 0x09, 0x80 },
{ 0x65, 0x49, 0x02 },
{ 0x65, 0x88, 0x24 },
{ 0x66, 0x27, 0x45 },
{ 0x66, 0x66, 0x67 },
{ 0x67, 0x05, 0x88 },
{ 0x67, 0x45, 0x10 },
{ 0x67, 0x84, 0x31 },
{ 0x68, 0x23, 0x53 },
{ 0x68, 0x62, 0x75 },
{ 0x69, 0x01, 0x96 },
{ 0x69, 0x41, 0x18 },
{ 0x69, 0x80, 0x39 },
{ 0x70, 0x19, 0x61 },
{ 0x70, 0x58, 0x82 },
{ 0x70, 0x98, 0x04 },
{ 0x71, 0x37, 0x25 },
{ 0x71, 0x76, 0x47 },
{ 0x72, 0x15, 0x69 },
{ 0x72, 0x54, 0x90 },
{ 0x72, 0x94, 0x12 },
{ 0x73, 0x33, 0x33 },
{ 0x73, 0x72, 0x55 },
{ 0x74, 0x11, 0x76 },
{ 0x74, 0x50, 0x98 },
{ 0x74, 0x90, 0x20 },
{ 0x75, 0x29, 0x41 },
{ 0x75, 0x68, 0x63 },
{ 0x76, 0x07, 0x84 },
{ 0x76, 0x47, 0x06 },
{ 0x76, 0x86, 0x27 },
{ 0x77, 0x25, 0x49 },
{ 0x77, 0x64, 0x71 },
{ 0x78, 0x03, 0x92 },
{ 0x78, 0x43, 0x14 },
{ 0x78, 0x82, 0x35 },
{ 0x79, 0x21, 0x57 },
{ 0x79, 0x60, 0x78 },
{ 0x80, 0x00, 0x00 },
{ 0x80, 0x39, 0x22 },
{ 0x80, 0x78, 0x43 },
{ 0x81, 0x17, 0x65 },
{ 0x81, 0x56, 0x86 },
{ 0x81, 0x96, 0x08 },
{ 0x82, 0x35, 0x29 },
{ 0x82, 0x74, 0x51 },
{ 0x83, 0x13, 0x73 },
{ 0x83, 0x52, 0x94 },
{ 0x83, 0x92, 0x16 },
{ 0x84, 0x31, 0x37 },
{ 0x84, 0x70, 0x59 },
{ 0x85, 0x09, 0x80 },
{ 0x85, 0x49, 0x02 },
{ 0x85, 0x88, 0x24 },
{ 0x86, 0x27, 0x45 },
{ 0x86, 0x66, 0x67 },
{ 0x87, 0x05, 0x88 },
{ 0x87, 0x45, 0x10 },
{ 0x87, 0x84, 0x31 },
{ 0x88, 0x23, 0x53 },
{ 0x88, 0x62, 0x75 },
{ 0x89, 0x01, 0x96 },
{ 0x89, 0x41, 0x18 },
{ 0x89, 0x80, 0x39 },
{ 0x90, 0x19, 0x61 },
{ 0x90, 0x58, 0x82 },
{ 0x90, 0x98, 0x04 },
{ 0x91, 0x37, 0x25 },
{ 0x91, 0x76, 0x47 },
{ 0x92, 0x15, 0x69 },
{ 0x92, 0x54, 0x90 },
{ 0x92, 0x94, 0x12 },
{ 0x93, 0x33, 0x33 },
{ 0x93, 0x72, 0x55 },
{ 0x94, 0x11, 0x76 },
{ 0x94, 0x50, 0x98 },
{ 0x94, 0x90, 0x20 },
{ 0x95, 0x29, 0x41 },
{ 0x95, 0x68, 0x63 },
{ 0x96, 0x07, 0x84 },
{ 0x96, 0x47, 0x06 },
{ 0x96, 0x86, 0x27 },
{ 0x97, 0x25, 0x49 },
{ 0x97, 0x64, 0x71 },
{ 0x98, 0x03, 0x92 },
{ 0x98, 0x43, 0x14 },
{ 0x98, 0x82, 0x35 },
{ 0x99, 0x21, 0x57 },
{ 0x99, 0x60, 0x78 },
{ 0x00, 0x00, 0x00 },
};
> On Nov 3, 2015, at 11:37 AM, Darin Adler <darin at apple.com> wrote:
>
>> On Nov 3, 2015, at 11:10 AM, Maciej Stachowiak <mjs at apple.com> wrote:
>>
>> Minimal strings should round trip ok, but will it still be accurate enough if the client attempts to do math with them?
>
> I was thinking about the same thing this morning.
>
> If we don’t want them minimal, then how many digits of precision would be the right number? I think we currently are just using the printf default precision.
>
> — Darin
> _______________________________________________
> webkit-dev mailing list
> webkit-dev at lists.webkit.org
> https://lists.webkit.org/mailman/listinfo/webkit-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20151103/c8ba481e/attachment-0001.html>
More information about the webkit-dev
mailing list