From 6bdbb45e88e7b88b294dfb6e4cb493cbc3c8cf74 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Sun, 13 Feb 2011 12:59:54 -0800 Subject: Merged core/ and stream/ -> src/. The split wasn't worth it. --- src/upb_decoder.c | 441 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 441 insertions(+) create mode 100644 src/upb_decoder.c (limited to 'src/upb_decoder.c') diff --git a/src/upb_decoder.c b/src/upb_decoder.c new file mode 100644 index 0000000..4a43c4b --- /dev/null +++ b/src/upb_decoder.c @@ -0,0 +1,441 @@ +/* + * upb - a minimalist implementation of protocol buffers. + * + * Copyright (c) 2008-2009 Joshua Haberman. See LICENSE for details. + */ + +#include "upb_decoder.h" + +#include +#include +#include +#include "upb_def.h" + +/* Pure Decoding **************************************************************/ + +// The key fast-path varint-decoding routine. Here we can assume we have at +// least UPB_MAX_VARINT_ENCODED_SIZE bytes available. There are a lot of +// possibilities for optimization/experimentation here. + +#ifdef USE_SSE_VARINT_DECODING +#include + +// This works, but is empirically slower than the branchy version below. Why? +// Most varints are very short. Next step: use branches for 1/2-byte varints, +// but use the SSE version for 3-10 byte varints. +INLINE bool upb_decode_varint_fast(const char **ptr, uint64_t *val, upb_status *s) { + const char *p = *ptr; + __m128i val128 = _mm_loadu_si128((void*)p); + unsigned int continuation_bits = _mm_movemask_epi8(val128); + unsigned int bsr_val = ~continuation_bits; + int varint_length = __builtin_ffs(bsr_val); + if (varint_length > 10) { + upb_seterr(s, UPB_ERROR, "Unterminated varint"); + return false; + } + + uint16_t twob; + memcpy(&twob, p, 2); + twob &= 0x7f7f; + twob = ((twob & 0xff00) >> 1) | (twob & 0xff); + + uint64_t eightb; + memcpy(&eightb, p + 2, 8); + eightb &= 0x7f7f7f7f7f7f7f7f; + eightb = ((eightb & 0xff00ff00ff00ff00) >> 1) | (eightb & 0x00ff00ff00ff00ff); + eightb = ((eightb & 0xffff0000ffff0000) >> 2) | (eightb & 0x0000ffff0000ffff); + eightb = ((eightb & 0xffffffff00000000) >> 4) | (eightb & 0x00000000ffffffff); + + uint64_t all_bits = twob | (eightb << 14); + int varint_bits = varint_length * 7; + uint64_t mask = varint_bits == 70 ? (uint64_t)-1 : (1ULL << (varint_bits)) - 1; + *val = all_bits & mask; + *ptr = p + varint_length; + return true; +} + +#else + +INLINE bool upb_decode_varint_fast(const char **ptr, uint64_t *val, upb_status *s) { + const char *p = *ptr; + uint32_t low, high = 0; + uint32_t b; + b = *(p++); low = (b & 0x7f) ; if(!(b & 0x80)) goto done; + b = *(p++); low |= (b & 0x7f) << 7; if(!(b & 0x80)) goto done; + b = *(p++); low |= (b & 0x7f) << 14; if(!(b & 0x80)) goto done; + b = *(p++); low |= (b & 0x7f) << 21; if(!(b & 0x80)) goto done; + b = *(p++); low |= (b & 0x7f) << 28; + high = (b & 0x7f) >> 4; if(!(b & 0x80)) goto done; + b = *(p++); high |= (b & 0x7f) << 3; if(!(b & 0x80)) goto done; + b = *(p++); high |= (b & 0x7f) << 10; if(!(b & 0x80)) goto done; + b = *(p++); high |= (b & 0x7f) << 17; if(!(b & 0x80)) goto done; + b = *(p++); high |= (b & 0x7f) << 24; if(!(b & 0x80)) goto done; + b = *(p++); high |= (b & 0x7f) << 31; if(!(b & 0x80)) goto done; + + upb_seterr(s, UPB_ERROR, "Unterminated varint"); + return false; + +done: + *val = ((uint64_t)high << 32) | low; + *ptr = p; + return true; +} + +#endif + + +/* Decoding/Buffering of individual values ************************************/ + +// Performs zig-zag decoding, which is used by sint32 and sint64. +INLINE int32_t upb_zzdec_32(uint32_t n) { return (n >> 1) ^ -(int32_t)(n & 1); } +INLINE int64_t upb_zzdec_64(uint64_t n) { return (n >> 1) ^ -(int64_t)(n & 1); } + +typedef struct { + // Our current position in the data buffer. + const char *ptr; + + // End of this submessage, relative to *ptr. + const char *submsg_end; + + // Number of bytes available at ptr. + size_t len; + + // Msgdef for the current level. + upb_msgdef *msgdef; +} upb_dstate; + +// Constant used to signal that the submessage is a group and therefore we +// don't know its end offset. This cannot be the offset of a real submessage +// end because it takes at least one byte to begin a submessage. +#define UPB_GROUP_END_OFFSET 0 +#define UPB_MAX_VARINT_ENCODED_SIZE 10 + +INLINE void upb_dstate_advance(upb_dstate *s, size_t len) { + s->ptr += len; + s->len -= len; +} + +INLINE void upb_dstate_setmsgend(upb_decoder *d, upb_dstate *s) { + s->submsg_end = (d->top->end_offset == UPB_GROUP_END_OFFSET) ? + (void*)UINTPTR_MAX : + upb_string_getrobuf(d->buf) + (d->top->end_offset - d->buf_stream_offset); +} + +static upb_flow_t upb_pop(upb_decoder *d, upb_dstate *s); + +// Called only from the slow path, this function copies the next "len" bytes +// from the stream to "data", adjusting the dstate appropriately. +static bool upb_getbuf(upb_decoder *d, void *data, size_t bytes_wanted, + upb_dstate *s) { + while (1) { + size_t to_copy = UPB_MIN(bytes_wanted, s->len); + memcpy(data, s->ptr, to_copy); + upb_dstate_advance(s, to_copy); + bytes_wanted -= to_copy; + if (bytes_wanted == 0) { + upb_dstate_setmsgend(d, s); + return true; + } + + // Get next buffer. + if (d->buf) d->buf_stream_offset += upb_string_len(d->buf); + upb_string_recycle(&d->buf); + if (!upb_bytesrc_getstr(d->bytesrc, d->buf, d->status)) return false; + s->ptr = upb_string_getrobuf(d->buf); + s->len = upb_string_len(d->buf); + } +} + +// We use this path when we don't have UPB_MAX_VARINT_ENCODED_SIZE contiguous +// bytes available in our current buffer. We don't inline this because we +// accept that it will be slow and we don't want to pay for two copies of it. +static bool upb_decode_varint_slow(upb_decoder *d, upb_dstate *s, + upb_value *val) { + char byte = 0x80; + uint64_t val64 = 0; + int bitpos; + for(bitpos = 0; + bitpos < 70 && (byte & 0x80) && upb_getbuf(d, &byte, 1, s); + bitpos += 7) + val64 |= ((uint64_t)byte & 0x7F) << bitpos; + + if(bitpos == 70) { + upb_seterr(d->status, UPB_ERROR, + "Varint was unterminated after 10 bytes.\n"); + return false; + } else if (d->status->code == UPB_EOF && bitpos == 0) { + // Regular EOF. + return false; + } else if (d->status->code == UPB_EOF && (byte & 0x80)) { + upb_seterr(d->status, UPB_ERROR, + "Provided data ended in the middle of a varint.\n"); + return false; + } else { + // Success. + upb_value_setraw(val, val64); + return true; + } +} + +typedef struct { + upb_wire_type_t wire_type; + upb_field_number_t field_number; +} upb_tag; + +INLINE bool upb_decode_tag(upb_decoder *d, upb_dstate *s, upb_tag *tag) { + const char *p = s->ptr; + uint32_t tag_int; + upb_value val; + // Nearly all tag varints will be either 1 byte (1-16) or 2 bytes (17-2048). + if (s->len < 2) goto slow; // unlikely. + tag_int = *p & 0x7f; + if ((*(p++) & 0x80) == 0) goto done; // predictable if fields are in order + tag_int |= (*p & 0x7f) << 7; + if ((*(p++) & 0x80) == 0) goto done; // likely +slow: + // Decode a full varint starting over from ptr. + if (!upb_decode_varint_slow(d, s, &val)) return false; + tag_int = upb_value_getint64(val); + p = s->ptr; // Trick the next line into not overwriting us. +done: + upb_dstate_advance(s, p - s->ptr); + tag->wire_type = (upb_wire_type_t)(tag_int & 0x07); + tag->field_number = tag_int >> 3; + return true; +} + +INLINE bool upb_decode_varint(upb_decoder *d, upb_dstate *s, upb_value *val) { + if (s->len >= 16) { + // Common (fast) case. + uint64_t val64; + const char *p = s->ptr; + if (!upb_decode_varint_fast(&p, &val64, d->status)) return false; + upb_dstate_advance(s, p - s->ptr); + upb_value_setraw(val, val64); + return true; + } else { + return upb_decode_varint_slow(d, s, val); + } +} + +INLINE bool upb_decode_fixed(upb_decoder *d, upb_wire_type_t wt, + upb_dstate *s, upb_value *val) { + static const char table[] = {0, 8, 0, 0, 0, 4}; + size_t bytes = table[wt]; + if (s->len >= bytes) { + // Common (fast) case. + memcpy(val, s->ptr, bytes); + upb_dstate_advance(s, bytes); + } else { + if (!upb_getbuf(d, val, bytes, s)) return false; + } + return true; +} + +// "val" initially holds the length of the string, this is replaced by the +// contents of the string. +INLINE bool upb_decode_string(upb_decoder *d, upb_value *val, upb_string **str, + upb_dstate *s) { + upb_string_recycle(str); + uint32_t strlen = upb_value_getint32(*val); + if (s->len >= strlen) { + // Common (fast) case. + upb_string_substr(*str, d->buf, s->ptr - upb_string_getrobuf(d->buf), strlen); + upb_dstate_advance(s, strlen); + } else { + if (!upb_getbuf(d, upb_string_getrwbuf(*str, strlen), strlen, s)) + return false; + } + upb_value_setstr(val, *str); + return true; +} + + +/* The main decoding loop *****************************************************/ + +extern upb_wire_type_t upb_expected_wire_types[]; +// Returns true if wt is the correct on-the-wire type for ft. +INLINE bool upb_check_type(upb_wire_type_t wt, upb_fieldtype_t ft) { + // This doesn't currently support packed arrays. + return upb_types[ft].native_wire_type == wt; +} + +static upb_flow_t upb_push(upb_decoder *d, upb_dstate *s, upb_fielddef *f, + upb_value submsg_len, upb_fieldtype_t type) { + d->top++; + if(d->top >= d->limit) { + upb_seterr(d->status, UPB_ERROR, "Nesting too deep."); + return UPB_ERROR; + } + d->top->end_offset = (type == UPB_TYPE(GROUP)) ? + UPB_GROUP_END_OFFSET : + d->buf_stream_offset + (s->ptr - upb_string_getrobuf(d->buf)) + + upb_value_getint32(submsg_len); + d->top->msgdef = upb_downcast_msgdef(f->def); + upb_dstate_setmsgend(d, s); + return upb_dispatch_startsubmsg(&d->dispatcher, f); +} + +static upb_flow_t upb_pop(upb_decoder *d, upb_dstate *s) { + d->top--; + upb_dstate_setmsgend(d, s); + return upb_dispatch_endsubmsg(&d->dispatcher); +} + +void upb_decoder_run(upb_src *src, upb_status *status) { + upb_decoder *d = (upb_decoder*)src; + d->status = status; + // We put our dstate on the stack so the compiler knows they can't be changed + // by external code (like when we dispatch a callback). We must be sure not + // to let its address escape this source file. + upb_dstate state = {NULL, (void*)0x1, 0, d->top->msgdef}; + +// TODO: handle UPB_SKIPSUBMSG +#define CHECK_FLOW(expr) if ((expr) == UPB_BREAK) { assert(!upb_ok(status)); goto err; } +#define CHECK(expr) if (!expr) { assert(!upb_ok(status)); goto err; } + + CHECK_FLOW(upb_dispatch_startmsg(&d->dispatcher)); + + // Main loop: executed once per tag/field pair. + while(1) { + // Check for end-of-submessage. + while (state.ptr >= state.submsg_end) { + if (state.ptr > state.submsg_end) { + upb_seterr(d->status, UPB_ERROR, "Bad submessage end."); + goto err; + } + CHECK_FLOW(upb_pop(d, &state)); + } + + // Parse/handle tag. + upb_tag tag; + if (!upb_decode_tag(d, &state, &tag)) { + if (status->code == UPB_EOF && d->top == d->stack) { + // Normal end-of-file. + upb_clearerr(status); + CHECK_FLOW(upb_dispatch_endmsg(&d->dispatcher)); + return; + } else { + if (status->code == UPB_EOF) { + upb_seterr(status, UPB_ERROR, + "Input ended in the middle of a submessage."); + } + goto err; + } + } + + // Decode wire data. Hopefully this branch will predict pretty well + // since most types will read a varint here. + upb_value val; + switch (tag.wire_type) { + case UPB_WIRE_TYPE_START_GROUP: + break; // Nothing to do now, below we will push appropriately. + case UPB_WIRE_TYPE_END_GROUP: + if(d->top->end_offset != UPB_GROUP_END_OFFSET) { + upb_seterr(status, UPB_ERROR, "Unexpected END_GROUP tag."); + goto err; + } + CHECK_FLOW(upb_pop(d, &state)); + continue; // We have no value to dispatch. + case UPB_WIRE_TYPE_VARINT: + case UPB_WIRE_TYPE_DELIMITED: + // For the delimited case we are parsing the length. + CHECK(upb_decode_varint(d, &state, &val)); + break; + case UPB_WIRE_TYPE_32BIT: + case UPB_WIRE_TYPE_64BIT: + CHECK(upb_decode_fixed(d, tag.wire_type, &state, &val)); + break; + } + + // Look up field by tag number. + upb_fielddef *f = upb_msgdef_itof(d->top->msgdef, tag.field_number); + + if (!f) { + if (tag.wire_type == UPB_WIRE_TYPE_DELIMITED) + CHECK(upb_decode_string(d, &val, &d->tmp, &state)); + CHECK_FLOW(upb_dispatch_unknownval(&d->dispatcher, tag.field_number, val)); + } else if (!upb_check_type(tag.wire_type, f->type)) { + // TODO: put more details in this error msg. + upb_seterr(status, UPB_ERROR, "Field had incorrect type, name: " UPB_STRFMT, UPB_STRARG(f->name)); + upb_printerr(status); + *(int*)0 = 0; + goto err; + } + + // Perform any further massaging of the data now that we have the fielddef. + // Now we can distinguish strings from submessages, and we know about + // zig-zag-encoded types. + // TODO: handle packed encoding. + // TODO: if we were being paranoid, we could check for 32-bit-varint types + // that the top 32 bits all match the highest bit of the low 32 bits. + // If this is not true we are losing data. But the main protobuf library + // doesn't check this, and it would slow us down, so pass for now. + switch (f->type) { + case UPB_TYPE(MESSAGE): + case UPB_TYPE(GROUP): + CHECK_FLOW(upb_push(d, &state, f, val, f->type)); + continue; // We have no value to dispatch. + case UPB_TYPE(STRING): + case UPB_TYPE(BYTES): + CHECK(upb_decode_string(d, &val, &d->tmp, &state)); + break; + case UPB_TYPE(SINT32): + upb_value_setint32(&val, upb_zzdec_32(upb_value_getint32(val))); + break; + case UPB_TYPE(SINT64): + upb_value_setint64(&val, upb_zzdec_64(upb_value_getint64(val))); + break; + default: +#ifndef NDEBUG + val.type = upb_types[f->type].inmemory_type; +#endif + break; // Other types need no further processing at this point. + } + CHECK_FLOW(upb_dispatch_value(&d->dispatcher, f, val)); + } + +err: + if (upb_ok(status)) { + upb_seterr(status, UPB_ERROR, "Callback returned UPB_BREAK"); + } +} + +void upb_decoder_sethandlers(upb_src *src, upb_handlers *handlers) { + upb_decoder *d = (upb_decoder*)src; + upb_dispatcher_reset(&d->dispatcher, handlers, false); + d->top = d->stack; + d->buf_stream_offset = 0; + d->top->msgdef = d->toplevel_msgdef; + // The top-level message is not delimited (we can keep receiving data for it + // indefinitely), so we treat it like a group. + d->top->end_offset = 0; +} + +void upb_decoder_init(upb_decoder *d, upb_msgdef *msgdef) { + static upb_src_vtbl vtbl = { + &upb_decoder_sethandlers, + &upb_decoder_run, + }; + upb_src_init(&d->src, &vtbl); + upb_dispatcher_init(&d->dispatcher); + d->toplevel_msgdef = msgdef; + d->limit = &d->stack[UPB_MAX_NESTING]; + d->buf = NULL; + d->tmp = NULL; +} + +void upb_decoder_reset(upb_decoder *d, upb_bytesrc *bytesrc) { + d->bytesrc = bytesrc; + d->top = &d->stack[0]; + d->top->msgdef = d->toplevel_msgdef; + // Never want to end top-level message, so treat it like a group. + d->top->end_offset = UPB_GROUP_END_OFFSET; +} + +void upb_decoder_uninit(upb_decoder *d) { + upb_string_unref(d->buf); + upb_string_unref(d->tmp); +} + +upb_src *upb_decoder_src(upb_decoder *d) { return &d->src; } -- cgit v1.2.3