1 /*
2 * Copyright (c) 2009-2021, Google LLC
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google LLC nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT,
20 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "upb/util/compare.h"
29
30 #include <stdlib.h>
31
32 #include "upb/upb.h"
33 #include "upb/wire/eps_copy_input_stream.h"
34 #include "upb/wire/reader.h"
35 #include "upb/wire/types.h"
36 // Must be last.
37 #include "upb/port/def.inc"
38
39 struct upb_UnknownFields;
40 typedef struct upb_UnknownFields upb_UnknownFields;
41
42 typedef struct {
43 uint32_t tag;
44 union {
45 uint64_t varint;
46 uint64_t uint64;
47 uint32_t uint32;
48 upb_StringView delimited;
49 upb_UnknownFields* group;
50 } data;
51 } upb_UnknownField;
52
53 struct upb_UnknownFields {
54 size_t size;
55 size_t capacity;
56 upb_UnknownField* fields;
57 };
58
59 typedef struct {
60 upb_EpsCopyInputStream stream;
61 upb_Arena* arena;
62 upb_UnknownField* tmp;
63 size_t tmp_size;
64 int depth;
65 upb_UnknownCompareResult status;
66 jmp_buf err;
67 } upb_UnknownField_Context;
68
upb_UnknownFields_OutOfMemory(upb_UnknownField_Context * ctx)69 UPB_NORETURN static void upb_UnknownFields_OutOfMemory(
70 upb_UnknownField_Context* ctx) {
71 ctx->status = kUpb_UnknownCompareResult_OutOfMemory;
72 UPB_LONGJMP(ctx->err, 1);
73 }
74
upb_UnknownFields_Grow(upb_UnknownField_Context * ctx,upb_UnknownField ** base,upb_UnknownField ** ptr,upb_UnknownField ** end)75 static void upb_UnknownFields_Grow(upb_UnknownField_Context* ctx,
76 upb_UnknownField** base,
77 upb_UnknownField** ptr,
78 upb_UnknownField** end) {
79 size_t old = (*ptr - *base);
80 size_t new = UPB_MAX(4, old * 2);
81
82 *base = upb_Arena_Realloc(ctx->arena, *base, old * sizeof(**base),
83 new * sizeof(**base));
84 if (!*base) upb_UnknownFields_OutOfMemory(ctx);
85
86 *ptr = *base + old;
87 *end = *base + new;
88 }
89
90 // We have to implement our own sort here, since qsort() is not an in-order
91 // sort. Here we use merge sort, the simplest in-order sort.
upb_UnknownFields_Merge(upb_UnknownField * arr,size_t start,size_t mid,size_t end,upb_UnknownField * tmp)92 static void upb_UnknownFields_Merge(upb_UnknownField* arr, size_t start,
93 size_t mid, size_t end,
94 upb_UnknownField* tmp) {
95 memcpy(tmp, &arr[start], (end - start) * sizeof(*tmp));
96
97 upb_UnknownField* ptr1 = tmp;
98 upb_UnknownField* end1 = &tmp[mid - start];
99 upb_UnknownField* ptr2 = &tmp[mid - start];
100 upb_UnknownField* end2 = &tmp[end - start];
101 upb_UnknownField* out = &arr[start];
102
103 while (ptr1 < end1 && ptr2 < end2) {
104 if (ptr1->tag <= ptr2->tag) {
105 *out++ = *ptr1++;
106 } else {
107 *out++ = *ptr2++;
108 }
109 }
110
111 if (ptr1 < end1) {
112 memcpy(out, ptr1, (end1 - ptr1) * sizeof(*out));
113 } else if (ptr2 < end2) {
114 memcpy(out, ptr1, (end2 - ptr2) * sizeof(*out));
115 }
116 }
117
upb_UnknownFields_SortRecursive(upb_UnknownField * arr,size_t start,size_t end,upb_UnknownField * tmp)118 static void upb_UnknownFields_SortRecursive(upb_UnknownField* arr, size_t start,
119 size_t end, upb_UnknownField* tmp) {
120 if (end - start > 1) {
121 size_t mid = start + ((end - start) / 2);
122 upb_UnknownFields_SortRecursive(arr, start, mid, tmp);
123 upb_UnknownFields_SortRecursive(arr, mid, end, tmp);
124 upb_UnknownFields_Merge(arr, start, mid, end, tmp);
125 }
126 }
127
upb_UnknownFields_Sort(upb_UnknownField_Context * ctx,upb_UnknownFields * fields)128 static void upb_UnknownFields_Sort(upb_UnknownField_Context* ctx,
129 upb_UnknownFields* fields) {
130 if (ctx->tmp_size < fields->size) {
131 ctx->tmp_size = UPB_MAX(8, ctx->tmp_size);
132 while (ctx->tmp_size < fields->size) ctx->tmp_size *= 2;
133 ctx->tmp = realloc(ctx->tmp, ctx->tmp_size * sizeof(*ctx->tmp));
134 }
135 upb_UnknownFields_SortRecursive(fields->fields, 0, fields->size, ctx->tmp);
136 }
137
upb_UnknownFields_DoBuild(upb_UnknownField_Context * ctx,const char ** buf)138 static upb_UnknownFields* upb_UnknownFields_DoBuild(
139 upb_UnknownField_Context* ctx, const char** buf) {
140 upb_UnknownField* arr_base = NULL;
141 upb_UnknownField* arr_ptr = NULL;
142 upb_UnknownField* arr_end = NULL;
143 const char* ptr = *buf;
144 uint32_t last_tag = 0;
145 bool sorted = true;
146 while (!upb_EpsCopyInputStream_IsDone(&ctx->stream, &ptr)) {
147 uint32_t tag;
148 ptr = upb_WireReader_ReadTag(ptr, &tag);
149 UPB_ASSERT(tag <= UINT32_MAX);
150 int wire_type = upb_WireReader_GetWireType(tag);
151 if (wire_type == kUpb_WireType_EndGroup) break;
152 if (tag < last_tag) sorted = false;
153 last_tag = tag;
154
155 if (arr_ptr == arr_end) {
156 upb_UnknownFields_Grow(ctx, &arr_base, &arr_ptr, &arr_end);
157 }
158 upb_UnknownField* field = arr_ptr;
159 field->tag = tag;
160 arr_ptr++;
161
162 switch (wire_type) {
163 case kUpb_WireType_Varint:
164 ptr = upb_WireReader_ReadVarint(ptr, &field->data.varint);
165 break;
166 case kUpb_WireType_64Bit:
167 ptr = upb_WireReader_ReadFixed64(ptr, &field->data.uint64);
168 break;
169 case kUpb_WireType_32Bit:
170 ptr = upb_WireReader_ReadFixed32(ptr, &field->data.uint32);
171 break;
172 case kUpb_WireType_Delimited: {
173 int size;
174 ptr = upb_WireReader_ReadSize(ptr, &size);
175 const char* s_ptr = ptr;
176 ptr = upb_EpsCopyInputStream_ReadStringAliased(&ctx->stream, &s_ptr,
177 size);
178 field->data.delimited.data = s_ptr;
179 field->data.delimited.size = size;
180 break;
181 }
182 case kUpb_WireType_StartGroup:
183 if (--ctx->depth == 0) {
184 ctx->status = kUpb_UnknownCompareResult_MaxDepthExceeded;
185 UPB_LONGJMP(ctx->err, 1);
186 }
187 field->data.group = upb_UnknownFields_DoBuild(ctx, &ptr);
188 ctx->depth++;
189 break;
190 default:
191 UPB_UNREACHABLE();
192 }
193 }
194
195 *buf = ptr;
196 upb_UnknownFields* ret = upb_Arena_Malloc(ctx->arena, sizeof(*ret));
197 if (!ret) upb_UnknownFields_OutOfMemory(ctx);
198 ret->fields = arr_base;
199 ret->size = arr_ptr - arr_base;
200 ret->capacity = arr_end - arr_base;
201 if (!sorted) {
202 upb_UnknownFields_Sort(ctx, ret);
203 }
204 return ret;
205 }
206
207 // Builds a upb_UnknownFields data structure from the binary data in buf.
upb_UnknownFields_Build(upb_UnknownField_Context * ctx,const char * ptr,size_t size)208 static upb_UnknownFields* upb_UnknownFields_Build(upb_UnknownField_Context* ctx,
209 const char* ptr,
210 size_t size) {
211 upb_EpsCopyInputStream_Init(&ctx->stream, &ptr, size, true);
212 upb_UnknownFields* fields = upb_UnknownFields_DoBuild(ctx, &ptr);
213 UPB_ASSERT(upb_EpsCopyInputStream_IsDone(&ctx->stream, &ptr) &&
214 !upb_EpsCopyInputStream_IsError(&ctx->stream));
215 return fields;
216 }
217
218 // Compares two sorted upb_UnknwonFields structures for equality.
upb_UnknownFields_IsEqual(const upb_UnknownFields * uf1,const upb_UnknownFields * uf2)219 static bool upb_UnknownFields_IsEqual(const upb_UnknownFields* uf1,
220 const upb_UnknownFields* uf2) {
221 if (uf1->size != uf2->size) return false;
222 for (size_t i = 0, n = uf1->size; i < n; i++) {
223 upb_UnknownField* f1 = &uf1->fields[i];
224 upb_UnknownField* f2 = &uf2->fields[i];
225 if (f1->tag != f2->tag) return false;
226 int wire_type = f1->tag & 7;
227 switch (wire_type) {
228 case kUpb_WireType_Varint:
229 if (f1->data.varint != f2->data.varint) return false;
230 break;
231 case kUpb_WireType_64Bit:
232 if (f1->data.uint64 != f2->data.uint64) return false;
233 break;
234 case kUpb_WireType_32Bit:
235 if (f1->data.uint32 != f2->data.uint32) return false;
236 break;
237 case kUpb_WireType_Delimited:
238 if (!upb_StringView_IsEqual(f1->data.delimited, f2->data.delimited)) {
239 return false;
240 }
241 break;
242 case kUpb_WireType_StartGroup:
243 if (!upb_UnknownFields_IsEqual(f1->data.group, f2->data.group)) {
244 return false;
245 }
246 break;
247 default:
248 UPB_UNREACHABLE();
249 }
250 }
251 return true;
252 }
253
upb_UnknownField_DoCompare(upb_UnknownField_Context * ctx,const char * buf1,size_t size1,const char * buf2,size_t size2)254 static upb_UnknownCompareResult upb_UnknownField_DoCompare(
255 upb_UnknownField_Context* ctx, const char* buf1, size_t size1,
256 const char* buf2, size_t size2) {
257 upb_UnknownCompareResult ret;
258 // First build both unknown fields into a sorted data structure (similar
259 // to the UnknownFieldSet in C++).
260 upb_UnknownFields* uf1 = upb_UnknownFields_Build(ctx, buf1, size1);
261 upb_UnknownFields* uf2 = upb_UnknownFields_Build(ctx, buf2, size2);
262
263 // Now perform the equality check on the sorted structures.
264 if (upb_UnknownFields_IsEqual(uf1, uf2)) {
265 ret = kUpb_UnknownCompareResult_Equal;
266 } else {
267 ret = kUpb_UnknownCompareResult_NotEqual;
268 }
269 return ret;
270 }
271
upb_UnknownField_Compare(upb_UnknownField_Context * const ctx,const char * const buf1,const size_t size1,const char * const buf2,const size_t size2)272 static upb_UnknownCompareResult upb_UnknownField_Compare(
273 upb_UnknownField_Context* const ctx, const char* const buf1,
274 const size_t size1, const char* const buf2, const size_t size2) {
275 upb_UnknownCompareResult ret;
276 if (UPB_SETJMP(ctx->err) == 0) {
277 ret = upb_UnknownField_DoCompare(ctx, buf1, size1, buf2, size2);
278 } else {
279 ret = ctx->status;
280 UPB_ASSERT(ret != kUpb_UnknownCompareResult_Equal);
281 }
282
283 upb_Arena_Free(ctx->arena);
284 free(ctx->tmp);
285 return ret;
286 }
287
upb_Message_UnknownFieldsAreEqual(const char * buf1,size_t size1,const char * buf2,size_t size2,int max_depth)288 upb_UnknownCompareResult upb_Message_UnknownFieldsAreEqual(const char* buf1,
289 size_t size1,
290 const char* buf2,
291 size_t size2,
292 int max_depth) {
293 if (size1 == 0 && size2 == 0) return kUpb_UnknownCompareResult_Equal;
294 if (size1 == 0 || size2 == 0) return kUpb_UnknownCompareResult_NotEqual;
295 if (memcmp(buf1, buf2, size1) == 0) return kUpb_UnknownCompareResult_Equal;
296
297 upb_UnknownField_Context ctx = {
298 .arena = upb_Arena_New(),
299 .depth = max_depth,
300 .tmp = NULL,
301 .tmp_size = 0,
302 .status = kUpb_UnknownCompareResult_Equal,
303 };
304
305 if (!ctx.arena) return kUpb_UnknownCompareResult_OutOfMemory;
306
307 return upb_UnknownField_Compare(&ctx, buf1, size1, buf2, size2);
308 }
309