diff options
| -rw-r--r-- | tests/pb/test_varint.c | 157 | ||||
| -rw-r--r-- | upb/pb/varint.c | 51 | ||||
| -rw-r--r-- | upb/pb/varint.int.h | 14 |
3 files changed, 0 insertions, 222 deletions
diff --git a/tests/pb/test_varint.c b/tests/pb/test_varint.c index eff03fa..f77eebd 100644 --- a/tests/pb/test_varint.c +++ b/tests/pb/test_varint.c @@ -86,168 +86,11 @@ static void test_varint_decoder(upb_decoderet (*decoder)(const char*)) { TEST_VARINT_DECODER(check2_branch32) TEST_VARINT_DECODER(check2_branch64) -TEST_VARINT_DECODER(check2_wright) -TEST_VARINT_DECODER(check2_massimino) int run_tests(int argc, char *argv[]) { UPB_UNUSED(argc); UPB_UNUSED(argv); test_check2_branch32(); test_check2_branch64(); - test_check2_wright(); - test_check2_massimino(); return 0; } - -#if 0 -static void test_get_v_uint32_t() -{ -#define TEST(name, bytes, val) {\ - upb_status status = UPB_STATUS_INIT; \ - const uint8_t name[] = bytes; \ - const uint8_t *name ## _buf = name; \ - uint32_t name ## _val = 0; \ - name ## _buf = upb_get_v_uint32_t(name, name + sizeof(name), &name ## _val, &status); \ - ASSERT(upb_ok(&status)); \ - ASSERT(name ## _val == val); \ - ASSERT(name ## _buf == name + sizeof(name) - 1); /* - 1 for NULL */ \ - /* Test NEED_MORE_DATA. */ \ - if(sizeof(name) > 2) { \ - name ## _buf = upb_get_v_uint32_t(name, name + sizeof(name) - 2, &name ## _val, &status); \ - ASSERT(status.code == UPB_STATUS_NEED_MORE_DATA); \ - } \ - } - - TEST(zero, "\x00", 0UL); - TEST(one, "\x01", 1UL); - TEST(twob, "\x81\x03", 0x181UL); - TEST(threeb, "\x81\x83\x07", 0x1c181UL); - TEST(fourb, "\x81\x83\x87\x0f", 0x1e1c181UL); - /* get_v_uint32_t truncates, so all the rest return the same thing. */ - TEST(fiveb, "\x81\x83\x87\x8f\x1f", 0xf1e1c181UL); - TEST(sixb, "\x81\x83\x87\x8f\x9f\x3f", 0xf1e1c181UL); - TEST(sevenb, "\x81\x83\x87\x8f\x9f\xbf\x7f", 0xf1e1c181UL); - TEST(eightb, "\x81\x83\x87\x8f\x9f\xbf\xff\x01", 0xf1e1c181UL); - TEST(nineb, "\x81\x83\x87\x8f\x9f\xbf\xff\x81\x03", 0xf1e1c181UL); - TEST(tenb, "\x81\x83\x87\x8f\x9f\xbf\xff\x81\x83\x07", 0xf1e1c181UL); -#undef TEST - - uint8_t twelvebyte[] = {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01, 0x01}; - uint32_t twelvebyte_val = 0; - upb_status status = UPB_STATUS_INIT; - /* A varint that terminates before hitting the end of the provided buffer, - * but in too many bytes (11 instead of 10). */ - upb_get_v_uint32_t(twelvebyte, twelvebyte + 12, &twelvebyte_val, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT); - - /* A varint that terminates simultaneously with the end of the provided - * buffer, but in too many bytes (11 instead of 10). */ - upb_reset(&status); - upb_get_v_uint32_t(twelvebyte, twelvebyte + 11, &twelvebyte_val, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT); - - /* A varint whose buffer ends on exactly the byte where the varint must - * terminate, but the final byte does not terminate. The absolutely most - * correct return code here is UPB_ERROR_UNTERMINATED_VARINT, because we know - * by this point that the varint does not properly terminate. But we also - * allow a return value of UPB_STATUS_NEED_MORE_DATA here, because it does not - * compromise overall correctness -- clients who supply more data later will - * then receive a UPB_ERROR_UNTERMINATED_VARINT error; clients who have no - * more data to supply will (rightly) conclude that their protobuf is corrupt. - */ - upb_reset(&status); - upb_get_v_uint32_t(twelvebyte, twelvebyte + 10, &twelvebyte_val, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT || - status.code == UPB_STATUS_NEED_MORE_DATA); - - upb_reset(&status); - upb_get_v_uint32_t(twelvebyte, twelvebyte + 9, &twelvebyte_val, &status); - ASSERT(status.code == UPB_STATUS_NEED_MORE_DATA); -} - -static void test_skip_v_uint64_t() -{ -#define TEST(name, bytes) {\ - upb_status status = UPB_STATUS_INIT; \ - const uint8_t name[] = bytes; \ - const uint8_t *name ## _buf = name; \ - name ## _buf = upb_skip_v_uint64_t(name ## _buf, name + sizeof(name), &status); \ - ASSERT(upb_ok(&status)); \ - ASSERT(name ## _buf == name + sizeof(name) - 1); /* - 1 for NULL */ \ - /* Test NEED_MORE_DATA. */ \ - if(sizeof(name) > 2) { \ - name ## _buf = upb_skip_v_uint64_t(name, name + sizeof(name) - 2, &status); \ - ASSERT(status.code == UPB_STATUS_NEED_MORE_DATA); \ - } \ - } - - TEST(zero, "\x00"); - TEST(one, "\x01"); - TEST(twob, "\x81\x03"); - TEST(threeb, "\x81\x83\x07"); - TEST(fourb, "\x81\x83\x87\x0f"); - TEST(fiveb, "\x81\x83\x87\x8f\x1f"); - TEST(sixb, "\x81\x83\x87\x8f\x9f\x3f"); - TEST(sevenb, "\x81\x83\x87\x8f\x9f\xbf\x7f"); - TEST(eightb, "\x81\x83\x87\x8f\x9f\xbf\xff\x01"); - TEST(nineb, "\x81\x83\x87\x8f\x9f\xbf\xff\x81\x03"); - TEST(tenb, "\x81\x83\x87\x8f\x9f\xbf\xff\x81\x83\x07"); -#undef TEST - - uint8_t twelvebyte[] = {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01, 0x01}; - upb_status status = UPB_STATUS_INIT; - /* A varint that terminates before hitting the end of the provided buffer, - * but in too many bytes (11 instead of 10). */ - upb_skip_v_uint64_t(twelvebyte, twelvebyte + 12, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT); - - /* A varint that terminates simultaneously with the end of the provided - * buffer, but in too many bytes (11 instead of 10). */ - upb_reset(&status); - upb_skip_v_uint64_t(twelvebyte, twelvebyte + 11, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT); - - /* A varint whose buffer ends on exactly the byte where the varint must - * terminate, but the final byte does not terminate. The absolutely most - * correct return code here is UPB_ERROR_UNTERMINATED_VARINT, because we know - * by this point that the varint does not properly terminate. But we also - * allow a return value of UPB_STATUS_NEED_MORE_DATA here, because it does not - * compromise overall correctness -- clients who supply more data later will - * then receive a UPB_ERROR_UNTERMINATED_VARINT error; clients who have no - * more data to supply will (rightly) conclude that their protobuf is corrupt. - */ - upb_reset(&status); - upb_skip_v_uint64_t(twelvebyte, twelvebyte + 10, &status); - ASSERT(status.code == UPB_ERROR_UNTERMINATED_VARINT || - status.code == UPB_STATUS_NEED_MORE_DATA); - - upb_reset(&status); - upb_skip_v_uint64_t(twelvebyte, twelvebyte + 9, &status); - ASSERT(status.code == UPB_STATUS_NEED_MORE_DATA); -} - -static void test_get_f_uint32_t() -{ -#define TEST(name, bytes, val) {\ - upb_status status = UPB_STATUS_INIT; \ - const uint8_t name[] = bytes; \ - const uint8_t *name ## _buf = name; \ - uint32_t name ## _val = 0; \ - name ## _buf = upb_get_f_uint32_t(name ## _buf, name + sizeof(name), &name ## _val, &status); \ - ASSERT(upb_ok(&status)); \ - ASSERT(name ## _val == val); \ - ASSERT(name ## _buf == name + sizeof(name) - 1); /* - 1 for NULL */ \ - } - - TEST(zero, "\x00\x00\x00\x00", 0x0UL); - TEST(one, "\x01\x00\x00\x00", 0x1UL); - - uint8_t threeb[] = {0x00, 0x00, 0x00}; - uint32_t threeb_val; - upb_status status = UPB_STATUS_INIT; - upb_get_f_uint32_t(threeb, threeb + sizeof(threeb), &threeb_val, &status); - ASSERT(status.code == UPB_STATUS_NEED_MORE_DATA); - -#undef TEST -} -#endif diff --git a/upb/pb/varint.c b/upb/pb/varint.c index 25cdd81..90f58a1 100644 --- a/upb/pb/varint.c +++ b/upb/pb/varint.c @@ -72,54 +72,3 @@ done: r.p = p; return r; } - -/* Given an encoded varint v, returns an integer with a single bit set that - * indicates the end of the varint. Subtracting one from this value will - * yield a mask that leaves only bits that are part of the varint. Returns - * 0 if the varint is unterminated. */ -static uint64_t upb_get_vstopbit(uint64_t v) { - uint64_t cbits = v | 0x7f7f7f7f7f7f7f7fULL; - return ~cbits & (cbits+1); -} - -/* A branchless decoder. Credit to Pascal Massimino for the bit-twiddling. */ -upb_decoderet upb_vdecode_max8_massimino(upb_decoderet r) { - uint64_t b; - uint64_t stop_bit; - upb_decoderet my_r; - memcpy(&b, r.p, sizeof(b)); - stop_bit = upb_get_vstopbit(b); - b = (b & 0x7f7f7f7f7f7f7f7fULL) & (stop_bit - 1); - b += b & 0x007f007f007f007fULL; - b += 3 * (b & 0x0000ffff0000ffffULL); - b += 15 * (b & 0x00000000ffffffffULL); - if (stop_bit == 0) { - /* Error: unterminated varint. */ - upb_decoderet err_r = {(void*)0, 0}; - return err_r; - } - my_r = upb_decoderet_make(r.p + ((__builtin_ctzll(stop_bit) + 1) / 8), - r.val | (b << 7)); - return my_r; -} - -/* A branchless decoder. Credit to Daniel Wright for the bit-twiddling. */ -upb_decoderet upb_vdecode_max8_wright(upb_decoderet r) { - uint64_t b; - uint64_t stop_bit; - upb_decoderet my_r; - memcpy(&b, r.p, sizeof(b)); - stop_bit = upb_get_vstopbit(b); - b &= (stop_bit - 1); - b = ((b & 0x7f007f007f007f00ULL) >> 1) | (b & 0x007f007f007f007fULL); - b = ((b & 0xffff0000ffff0000ULL) >> 2) | (b & 0x0000ffff0000ffffULL); - b = ((b & 0xffffffff00000000ULL) >> 4) | (b & 0x00000000ffffffffULL); - if (stop_bit == 0) { - /* Error: unterminated varint. */ - upb_decoderet err_r = {(void*)0, 0}; - return err_r; - } - my_r = upb_decoderet_make(r.p + ((__builtin_ctzll(stop_bit) + 1) / 8), - r.val | (b << 14)); - return my_r; -} diff --git a/upb/pb/varint.int.h b/upb/pb/varint.int.h index c8d4929..3ef84fb 100644 --- a/upb/pb/varint.int.h +++ b/upb/pb/varint.int.h @@ -62,16 +62,8 @@ UPB_INLINE upb_decoderet upb_decoderet_make(const char *p, uint64_t val) { return ret; } -/* Four functions for decoding a varint of at most eight bytes. They are all - * functionally identical, but are implemented in different ways and likely have - * different performance profiles. We keep them around for performance testing. - * - * Note that these functions may not read byte-by-byte, so they must not be used - * unless there are at least eight bytes left in the buffer! */ upb_decoderet upb_vdecode_max8_branch32(upb_decoderet r); upb_decoderet upb_vdecode_max8_branch64(upb_decoderet r); -upb_decoderet upb_vdecode_max8_wright(upb_decoderet r); -upb_decoderet upb_vdecode_max8_massimino(upb_decoderet r); /* Template for a function that checks the first two bytes with branching * and dispatches 2-10 bytes with a separate function. Note that this may read @@ -96,8 +88,6 @@ UPB_INLINE upb_decoderet upb_vdecode_check2_ ## name(const char *_p) { \ UPB_VARINT_DECODER_CHECK2(branch32, upb_vdecode_max8_branch32) UPB_VARINT_DECODER_CHECK2(branch64, upb_vdecode_max8_branch64) -UPB_VARINT_DECODER_CHECK2(wright, upb_vdecode_max8_wright) -UPB_VARINT_DECODER_CHECK2(massimino, upb_vdecode_max8_massimino) #undef UPB_VARINT_DECODER_CHECK2 /* Our canonical functions for decoding varints, based on the currently @@ -109,10 +99,6 @@ UPB_INLINE upb_decoderet upb_vdecode_fast(const char *p) { return upb_vdecode_check2_branch32(p); } -UPB_INLINE upb_decoderet upb_vdecode_max8_fast(upb_decoderet r) { - return upb_vdecode_max8_massimino(r); -} - /* Encoding *******************************************************************/ |