1 /* -*- Mode: C; tab-width: 4 -*-
2  *
3  * Copyright (c) 2002-2003 Apple Computer, Inc. All rights reserved.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16 
17     Change History (most recent first):
18 
19 $Log: DNSCommon.c,v $
20 Revision 1.100.2.1  2006/08/29 06:24:22  cheshire
21 Re-licensed mDNSResponder daemon source code under Apache License, Version 2.0
22 
23 Revision 1.100  2006/06/08 22:58:46  cheshire
24 <rdar://problem/4335605> IPv6 link-local address prefix is FE80::/10, not FE80::/16
25 
26 Revision 1.99  2006/05/18 01:32:33  cheshire
27 <rdar://problem/4472706> iChat: Lost connection with Bonjour
28 (mDNSResponder insufficiently defensive against malformed browsing PTR responses)
29 
30 Revision 1.98  2006/03/19 17:00:58  cheshire
31 Define symbol MaxMsg instead of using hard-coded constant value '80'
32 
33 Revision 1.97  2006/03/18 21:47:56  cheshire
34 <rdar://problem/4073825> Improve logic for delaying packets after repeated interface transitions
35 
36 Revision 1.96  2006/03/10 21:51:42  cheshire
37 <rdar://problem/4111464> After record update, old record sometimes remains in cache
38 Split out SameRDataBody() into a separate routine so it can be called from other code
39 
40 Revision 1.95  2006/03/08 22:43:11  cheshire
41 Use "localdomain" symbol instead of literal string
42 
43 Revision 1.94  2006/03/02 21:59:55  cheshire
44 <rdar://problem/4395331> Spurious warning "GetLargeResourceRecord: m->rec appears to be already in use"
45 Improve sanity checks & debugging support in GetLargeResourceRecord()
46 
47 Revision 1.93  2006/03/02 20:30:47  cheshire
48 Improved GetRRDisplayString to also show priority, weight, and port for SRV records
49 
50 Revision 1.92  2005/09/16 21:06:49  cheshire
51 Use mDNS_TimeNow_NoLock macro, instead of writing "mDNSPlatformRawTime() + m->timenow_adjust" all over the place
52 
53 Revision 1.91  2005/07/10 22:10:37  cheshire
54 The getOptRdata routine implicitly assumes the destination ResourceRecord is large enough to
55 hold MaximumRDSize bytes, but its parameter was a generic ResourceRecord, which need not be that
56 large. Changing the parameter to a LargeCacheRecord makes it clearer what the routine requires.
57 
58 Revision 1.90  2005/03/21 00:33:51  shersche
59 <rdar://problem/4021486> Fix build warnings on Win32 platform
60 
61 Revision 1.89  2005/03/17 18:59:38  ksekar
62 <rdar://problem/4012279> Properly parse multiple LLQ Options per packet on Windows
63 
64 Revision 1.88  2005/03/16 00:42:32  ksekar
65 <rdar://problem/4012279> Long-lived queries not working on Windows
66 
67 Revision 1.87  2005/02/25 04:21:00  cheshire
68 <rdar://problem/4015377> mDNS -F returns the same domain multiple times with different casing
69 
70 Revision 1.86  2005/02/18 00:43:12  cheshire
71 <rdar://problem/4010245> mDNSResponder should auto-truncate service names that are too long
72 
73 Revision 1.85  2005/02/10 22:35:17  cheshire
74 <rdar://problem/3727944> Update name
75 
76 Revision 1.84  2005/02/03 00:44:38  cheshire
77 <rdar://problem/3986663> DNSServiceUpdateRecord returns kDNSServiceErr_Invalid when rdlen=0, rdata=NULL
78 
79 Revision 1.83  2005/01/27 22:57:55  cheshire
80 Fix compile errors on gcc4
81 
82 Revision 1.82  2005/01/19 03:27:03  cheshire
83 <rdar://problem/3961051> CPU Spin in mDNSResponder
84 GetNextScheduledEvent() needs to check LocalRecordReady()
85 
86 Revision 1.81  2004/12/18 03:13:45  cheshire
87 <rdar://problem/3751638> kDNSServiceInterfaceIndexLocalOnly should return all local records
88 
89 Revision 1.80  2004/12/16 21:46:43  cheshire
90 Add DNSTypeName case for kDNSType_SOA
91 
92 Revision 1.79  2004/12/16 21:38:37  cheshire
93 Add DNSTypeName case for kDNSType_NS
94 
95 Revision 1.78  2004/12/16 21:27:37  ksekar
96 Fixed build failures when compiled with verbose debugging messages
97 
98 Revision 1.77  2004/12/16 20:12:59  cheshire
99 <rdar://problem/3324626> Cache memory management improvements
100 
101 Revision 1.76  2004/12/16 08:05:29  shersche
102 Remove extranenous semicolons that cause compilation errors on Windows
103 
104 Revision 1.75  2004/12/15 02:11:22  ksekar
105 <rdar://problem/3917317> Don't check for Dynamic DNS hostname uniqueness
106 
107 Revision 1.74  2004/12/09 22:49:15  ksekar
108 <rdar://problem/3913653> Wide-Area Goodbyes broken
109 
110 Revision 1.73  2004/12/07 22:49:06  cheshire
111 <rdar://problem/3908850> BIND doesn't allow zero-length TXT records
112 
113 Revision 1.72  2004/12/06 21:15:20  ksekar
114 <rdar://problem/3884386> mDNSResponder crashed in CheckServiceRegistrations
115 
116 Revision 1.71  2004/12/04 02:12:45  cheshire
117 <rdar://problem/3517236> mDNSResponder puts LargeCacheRecord on the stack
118 
119 Revision 1.70  2004/12/03 19:52:44  ksekar
120 Use PutResourceRecordTTLJumbo for putDeletionRecord()
121 
122 Revision 1.69  2004/12/03 07:20:50  ksekar
123 <rdar://problem/3674208> Wide-Area: Registration of large TXT record fails
124 
125 Revision 1.68  2004/11/24 00:10:43  cheshire
126 <rdar://problem/3869241> For unicast operations, verify that service types are legal
127 
128 Revision 1.67  2004/10/26 03:52:02  cheshire
129 Update checkin comments
130 
131 Revision 1.66  2004/10/23 01:16:00  cheshire
132 <rdar://problem/3851677> uDNS operations not always reliable on multi-homed hosts
133 
134 Revision 1.65  2004/10/20 02:15:09  cheshire
135 Add case in GetRRDisplayString() to display NS rdata
136 
137 Revision 1.64  2004/10/13 00:24:02  cheshire
138 Disable "array is too small to include a terminating null character" warning on Windows
139 
140 Revision 1.63  2004/10/10 06:57:14  cheshire
141 Change definition of "localdomain" to make code compile a little smaller
142 
143 Revision 1.62  2004/10/06 01:44:19  cheshire
144 <rdar://problem/3813936> Resolving too quickly sometimes returns stale TXT record
145 
146 Revision 1.61  2004/09/30 00:24:56  ksekar
147 <rdar://problem/3695802> Dynamically update default registration domains on config change
148 
149 Revision 1.60  2004/09/27 23:25:30  cheshire
150 Fix compiler warning: soa.serial is signed, not unsigned
151 
152 Revision 1.59  2004/09/27 22:53:45  ksekar
153 Fixed getLargeResourceRecord for SOA rdata.
154 
155 Revision 1.58  2004/09/25 02:41:39  cheshire
156 <rdar://problem/3637266> Deliver near-pending "remove" events before new "add" events
157 
158 Revision 1.57  2004/09/25 02:24:27  cheshire
159 Removed unused rr->UseCount
160 
161 Revision 1.56  2004/09/24 20:57:39  cheshire
162 <rdar://problem/3680902> Eliminate inappropriate casts that cause misaligned-address errors
163 
164 Revision 1.55  2004/09/17 01:08:48  cheshire
165 Renamed mDNSClientAPI.h to mDNSEmbeddedAPI.h
166   The name "mDNSClientAPI.h" is misleading to new developers looking at this code. The interfaces
167   declared in that file are ONLY appropriate to single-address-space embedded applications.
168   For clients on general-purpose computers, the interfaces defined in dns_sd.h should be used.
169 
170 Revision 1.54  2004/09/17 00:49:51  cheshire
171 Get rid of now-unused GetResourceRecord -- the correct (safe) routine to use
172 is GetLargeResourceRecord
173 
174 Revision 1.53  2004/09/17 00:31:51  cheshire
175 For consistency with ipv6, renamed rdata field 'ip' to 'ipv4'
176 
177 Revision 1.52  2004/09/17 00:19:10  cheshire
178 For consistency with AllDNSLinkGroupv6, rename AllDNSLinkGroup to AllDNSLinkGroupv4
179 
180 Revision 1.51  2004/09/16 02:29:39  cheshire
181 Moved mDNS_Lock/mDNS_Unlock to DNSCommon.c; Added necessary locking around
182 uDNS_ReceiveMsg, uDNS_StartQuery, uDNS_UpdateRecord, uDNS_RegisterService
183 
184 Revision 1.50  2004/09/16 01:58:14  cheshire
185 Fix compiler warnings
186 
187 Revision 1.49  2004/09/14 23:42:35  cheshire
188 <rdar://problem/3801296> Need to seed random number generator from platform-layer data
189 
190 Revision 1.48  2004/09/14 23:27:46  cheshire
191 Fix compile errors
192 
193 Revision 1.47  2004/08/25 02:50:04  cheshire
194 <rdar://problem/3561220> Browses are no longer piggybacking on other browses
195 Make mDNSSameAddress() recognise that two mDNSAddrType_None addresses are necessarily equal
196 
197 Revision 1.46  2004/08/18 17:35:40  ksekar
198 <rdar://problem/3651443>: Feature #9586: Need support for Legacy NAT gateways
199 
200 Revision 1.45  2004/08/15 18:26:00  cheshire
201 Don't use strcpy() on "struct domainname" objects; use AssignDomainName() instead
202 (A "struct domainname" is a collection of packed pascal strings, not a C string.)
203 
204 Revision 1.44  2004/08/13 23:46:58  cheshire
205 "asyncronous" -> "asynchronous"
206 
207 Revision 1.43  2004/08/12 02:55:46  ksekar
208 Fix param order error moving putPrereqNameNotInUse from uDNS.c using
209 ustrcpy macro to DNSCommon.c using mDNSPlatformStrCopy().
210 
211 Revision 1.42  2004/08/10 23:19:14  ksekar
212 <rdar://problem/3722542>: DNS Extension daemon for Wide Area Service Discovery
213 Moved routines/constants to allow extern access for garbage collection daemon
214 
215 Revision 1.41  2004/08/10 01:10:01  cheshire
216 <rdar://problem/3588761> Current method of doing subtypes causes name collisions
217 Minor revision from Roger Pantos
218 
219 Revision 1.40  2004/08/04 22:10:46  cheshire
220 <rdar://problem/3588761> Current method of doing subtypes causes name collisions
221 Change to use "._sub." instead of ".s." to mark subtypes.
222 
223 Revision 1.39  2004/07/13 21:24:24  rpantos
224 Fix for <rdar://problem/3701120>.
225 
226 Revision 1.38  2004/06/18 21:08:58  cheshire
227 <rdar://problem/3540040> Applications are registering invalid records
228 Attempts to create domain names like "www..apple.com." now logged to aid debugging
229 
230 Revision 1.37  2004/06/18 20:25:42  cheshire
231 <rdar://problem/3488547> Add a syslog message if someone tries to use "local.arpa".
232 
233 Revision 1.36  2004/06/18 19:09:59  cheshire
234 <rdar://problem/3588761> Current method of doing subtypes causes name collisions
235 
236 Revision 1.35  2004/06/05 00:14:44  cheshire
237 Fix signed/unsigned and other compiler warnings
238 
239 Revision 1.34  2004/06/04 00:25:25  cheshire
240 Fix misaligned write exception that occurs on some platforms
241 
242 Revision 1.33  2004/06/04 00:16:18  cheshire
243 Remove non-portable use of 'inline'
244 
245 Revision 1.32  2004/06/03 03:09:58  ksekar
246 <rdar://problem/3668626>: Garbage Collection for Dynamic Updates
247 
248 Revision 1.31  2004/05/28 23:42:36  ksekar
249 <rdar://problem/3258021>: Feature: DNS server->client notification on record changes (#7805)
250 
251 Revision 1.30  2004/05/26 09:08:04  bradley
252 Added cast to correct structure pointer when allocating domain name list element to fix C++ builds.
253 
254 Revision 1.29  2004/05/18 23:51:25  cheshire
255 Tidy up all checkin comments to use consistent "<rdar://problem/xxxxxxx>" format for bug numbers
256 
257 Revision 1.28  2004/05/13 04:54:20  ksekar
258 Unified list copy/free code.  Added symetric list for
259 
260 Revision 1.27  2004/04/22 20:29:07  cheshire
261 Log error message if no count field passed to PutResourceRecordTTL()
262 
263 Revision 1.26  2004/04/22 04:07:01  cheshire
264 Fix from Bob Bradley: Don't try to do inline functions on compilers that don't support it
265 
266 Revision 1.25  2004/04/22 03:05:28  cheshire
267 kDNSClass_ANY should be kDNSQClass_ANY
268 
269 Revision 1.24  2004/04/22 02:51:20  cheshire
270 Use common code for HINFO/TXT and TSIG cases in putRData
271 
272 Revision 1.23  2004/04/15 00:51:28  bradley
273 Minor tweaks for Windows and C++ builds. Added casts for signed/unsigned integers and 64-bit pointers.
274 Prefix some functions with mDNS to avoid conflicts. Disable benign warnings on Microsoft compilers.
275 
276 Revision 1.22  2004/04/14 23:09:28  ksekar
277 Support for TSIG signed dynamic updates.
278 
279 Revision 1.21  2004/04/09 16:47:28  cheshire
280 <rdar://problem/3617655>: mDNSResponder escape handling inconsistent with BIND
281 
282 Revision 1.20  2004/04/09 16:37:15  cheshire
283 Suggestion from Bob Bradley:
284 Move NumCacheRecordsForInterfaceID() to DNSCommon.c so it's available to all platform layers
285 
286 Revision 1.19  2004/04/02 19:34:38  cheshire
287 Fix broken comment
288 
289 Revision 1.18  2004/03/30 06:45:00  cheshire
290 Compiler warning fixes from Don Woodward at Roku Labs
291 
292 Revision 1.17  2004/03/19 22:25:20  cheshire
293 <rdar://problem/3579561>: Need to limit service types to fourteen characters
294 Won't actually do this for now, but keep the code around just in case
295 
296 Revision 1.16  2004/03/08 02:45:35  cheshire
297 Minor change to make a couple of the log messages a bit shorter
298 
299 Revision 1.15  2004/03/08 02:44:09  cheshire
300 <rdar://problem/3579561>: Need to limit service types to fourteen characters
301 
302 Revision 1.14  2004/02/21 02:06:24  cheshire
303 Can't use anonymous unions -- they're non-standard and don't work on all compilers
304 
305 Revision 1.13  2004/02/06 23:04:18  ksekar
306 Basic Dynamic Update support via mDNS_Register (dissabled via
307 UNICAST_REGISTRATION #define)
308 
309 Revision 1.12  2004/02/03 22:37:10  cheshire
310 Delete unused (commented-out) code
311 
312 Revision 1.11  2004/02/03 22:35:34  cheshire
313 <rdar://problem/3548256>: Should not allow empty string for resolve domain
314 
315 Revision 1.10  2004/02/03 19:47:36  ksekar
316 Added an asynchronous state machine mechanism to uDNS.c, including
317 calls to find the parent zone for a domain name.  Changes include code
318 in repository previously dissabled via "#if 0 incomplete".  Codepath
319 is currently unused, and will be called to create update records, etc.
320 
321 Revision 1.9  2004/01/27 20:15:22  cheshire
322 <rdar://problem/3541288>: Time to prune obsolete code for listening on port 53
323 
324 Revision 1.8  2004/01/24 23:24:36  cheshire
325 Expanded out the list of local domains to reduce risk of mistakes in future
326 
327 Revision 1.7  2004/01/24 08:32:30  bradley
328 Mask values with 0xFF before casting to avoid runtime truncation errors on Windows debug builds.
329 Separated octal-escaped sequences preceding decimal digits to avoid errors with some compilers wanting
330 to signal potentially hidden errors about the subsequent digit not being part of the octal sequence.
331 
332 Revision 1.6  2004/01/24 04:59:15  cheshire
333 Fixes so that Posix/Linux, OS9, Windows, and VxWorks targets build again
334 
335 Revision 1.5  2004/01/23 23:23:14  ksekar
336 Added TCP support for truncated unicast messages.
337 
338 Revision 1.4  2004/01/22 02:15:33  cheshire
339 <rdar://problem/3536597>: Link-local reverse-mapping domains need to be resolved using link-local multicast
340 
341 Revision 1.3  2004/01/21 21:16:29  cheshire
342 Minor tidy-up: Deleted a bunch of blank lines, trailing spaces, tabs, etc.
343 
344 Revision 1.2  2003/12/13 05:47:48  bradley
345 Made local ptr const to fix error when assigning from const structure. Disable benign conditional
346 expression is constant warning when building with Microsoft compilers.
347 
348 Revision 1.1  2003/12/13 03:05:27  ksekar
349 <rdar://problem/3192548>: DynDNS: Unicast query of service records
350 
351  */
352 
353 #pragma ident	"%Z%%M%	%I%	%E% SMI"
354 
355 // Set mDNS_InstantiateInlines to tell mDNSEmbeddedAPI.h to instantiate inline functions, if necessary
356 #define mDNS_InstantiateInlines 1
357 #include "DNSCommon.h"
358 
359 // Disable certain benign warnings with Microsoft compilers
360 #if (defined(_MSC_VER))
361 	// Disable "conditional expression is constant" warning for debug macros.
362 	// Otherwise, this generates warnings for the perfectly natural construct "while(1)"
363 	// If someone knows a variant way of writing "while(1)" that doesn't generate warning messages, please let us know
364 	#pragma warning(disable:4127)
365 	// Disable "array is too small to include a terminating null character" warning
366 	// -- domain labels have an initial length byte, not a terminating null character
367 	#pragma warning(disable:4295)
368 #endif
369 
370 // ***************************************************************************
371 #if COMPILER_LIKES_PRAGMA_MARK
372 #pragma mark -
373 #pragma mark - DNameList copy/deallocation routines
374 #endif
375 
376 mDNSexport DNameListElem *mDNS_CopyDNameList(const DNameListElem *orig)
377 	{
378 	DNameListElem *copy = mDNSNULL, *newelem;
379 	const DNameListElem *ptr;
380 
381 	for (ptr = orig; ptr; ptr = ptr->next)
382 		{
383 		newelem = (DNameListElem*)mDNSPlatformMemAllocate(sizeof(DNameListElem));
384 		if (!newelem) { LogMsg("ERROR: malloc"); return mDNSNULL; }
385 		AssignDomainName(&newelem->name, &ptr->name);
386 		newelem->next = copy;
387 		copy = newelem;
388 		}
389 	return copy;
390 	}
391 
392 mDNSexport void mDNS_FreeDNameList(DNameListElem *list)
393 	{
394 	DNameListElem *fptr;
395 
396 	while (list)
397 		{
398 		fptr = list;
399 		list = list->next;
400 		mDNSPlatformMemFree(fptr);
401 		}
402 	}
403 
404 // ***************************************************************************
405 #if COMPILER_LIKES_PRAGMA_MARK
406 #pragma mark -
407 #pragma mark - General Utility Functions
408 #endif
409 
410 // return true for RFC1918 private addresses
411 mDNSexport mDNSBool IsPrivateV4Addr(mDNSAddr *addr)
412 	{
413 	mDNSu8 *b;
414 
415 	if (addr->type != mDNSAddrType_IPv4) return mDNSfalse;
416 	b = addr->ip.v4.b;
417 
418 	return ((b[0] == 10) ||                              // 10/8 prefix
419 			(b[0] == 172 && b[1] > 15 && b[1] < 32) ||   // 172.16/12
420 			(b[0] == 192 && b[1] == 168));               // 192.168/16
421 	}
422 
423 mDNSexport const NetworkInterfaceInfo *GetFirstActiveInterface(const NetworkInterfaceInfo *intf)
424 	{
425 	while (intf && !intf->InterfaceActive) intf = intf->next;
426 	return(intf);
427 	}
428 
429 mDNSexport mDNSInterfaceID GetNextActiveInterfaceID(const NetworkInterfaceInfo *intf)
430 	{
431 	const NetworkInterfaceInfo *next = GetFirstActiveInterface(intf->next);
432 	if (next) return(next->InterfaceID); else return(mDNSNULL);
433 	}
434 
435 mDNSexport mDNSu32 NumCacheRecordsForInterfaceID(const mDNS *const m, mDNSInterfaceID id)
436 	{
437 	mDNSu32 slot, used = 0;
438 	CacheGroup *cg;
439 	CacheRecord *rr;
440 	FORALL_CACHERECORDS(slot, cg, rr)
441 		if (rr->resrec.InterfaceID == id) used++;
442 	return(used);
443 	}
444 
445 mDNSexport char *DNSTypeName(mDNSu16 rrtype)
446 	{
447 	switch (rrtype)
448 		{
449 		case kDNSType_A:    return("Addr");
450 		case kDNSType_NS:   return("NS");
451 		case kDNSType_CNAME:return("CNAME");
452 		case kDNSType_SOA:  return("SOA");
453 		case kDNSType_NULL: return("NULL");
454 		case kDNSType_PTR:  return("PTR");
455 		case kDNSType_HINFO:return("HINFO");
456 		case kDNSType_TXT:  return("TXT");
457 		case kDNSType_AAAA: return("AAAA");
458 		case kDNSType_SRV:  return("SRV");
459 		case kDNSQType_ANY: return("ANY");
460 		default:			{
461 							static char buffer[16];
462 							mDNS_snprintf(buffer, sizeof(buffer), "(%d)", rrtype);
463 							return(buffer);
464 							}
465 		}
466 	}
467 
468 // Note slight bug: this code uses the rdlength from the ResourceRecord object, to display
469 // the rdata from the RDataBody object. Sometimes this could be the wrong length -- but as
470 // long as this routine is only used for debugging messages, it probably isn't a big problem.
471 mDNSexport char *GetRRDisplayString_rdb(const ResourceRecord *rr, RDataBody *rd, char *buffer)
472 	{
473 	#define Max (MaxMsg-1)
474 	char *ptr = buffer;
475 	mDNSu32 length = mDNS_snprintf(buffer, Max, "%4d %##s %s ", rr->rdlength, rr->name->c, DNSTypeName(rr->rrtype));
476 	switch (rr->rrtype)
477 		{
478 		case kDNSType_A:	mDNS_snprintf(buffer+length, Max-length, "%.4a", &rd->ipv4);          break;
479 
480 		case kDNSType_NS:	// Same as PTR
481 		case kDNSType_CNAME:// Same as PTR
482 		case kDNSType_PTR:	mDNS_snprintf(buffer+length, Max-length, "%##s", rd->name.c);       break;
483 
484 		case kDNSType_HINFO:// Display this the same as TXT (just show first string)
485 		case kDNSType_TXT:  mDNS_snprintf(buffer+length, Max-length, "%#s", rd->txt.c);         break;
486 
487 		case kDNSType_AAAA:	mDNS_snprintf(buffer+length, Max-length, "%.16a", &rd->ipv6);       break;
488 		case kDNSType_SRV:	mDNS_snprintf(buffer+length, Max-length, "%u %u %u %##s",
489 								rd->srv.priority, rd->srv.weight, mDNSVal16(rd->srv.port), rd->srv.target.c); break;
490 		default:			mDNS_snprintf(buffer+length, Max-length, "RDLen %d: %s", rr->rdlength, rd->data);  break;
491 		}
492 	for (ptr = buffer; *ptr; ptr++) if (*ptr < ' ') *ptr='.';
493 	return(buffer);
494 	}
495 
496 mDNSexport mDNSu32 mDNSRandom(mDNSu32 max)
497 	{
498 	static mDNSu32 seed = 0;
499 	mDNSu32 mask = 1;
500 
501 	if (!seed)
502 		{
503 		int i;
504 		seed = mDNSPlatformRandomSeed();				// Pick an initial seed
505 		for (i=0; i<100; i++) seed = seed * 21 + 1;		// And mix it up a bit
506 		}
507 	while (mask < max) mask = (mask << 1) | 1;
508 	do seed = seed * 21 + 1; while ((seed & mask) > max);
509 	return (seed & mask);
510 	}
511 
512 mDNSexport mDNSu32 mDNSRandomFromFixedSeed(mDNSu32 seed, mDNSu32 max)
513 	{
514 	mDNSu32 mask = 1;
515 	while (mask < max) mask = (mask << 1) | 1;
516 	do seed = seed * 21 + 1; while ((seed & mask) > max);
517 	return (seed & mask);
518 	}
519 
520 mDNSexport mDNSBool mDNSSameAddress(const mDNSAddr *ip1, const mDNSAddr *ip2)
521 	{
522 	if (ip1->type == ip2->type)
523 		{
524 		switch (ip1->type)
525 			{
526 			case mDNSAddrType_None : return(mDNStrue); // Empty addresses have no data and are therefore always equal
527 			case mDNSAddrType_IPv4 : return(mDNSBool)(mDNSSameIPv4Address(ip1->ip.v4, ip2->ip.v4));
528 			case mDNSAddrType_IPv6 : return(mDNSBool)(mDNSSameIPv6Address(ip1->ip.v6, ip2->ip.v6));
529 			}
530 		}
531 	return(mDNSfalse);
532 	}
533 
534 mDNSexport mDNSBool mDNSAddrIsDNSMulticast(const mDNSAddr *ip)
535 	{
536 	switch(ip->type)
537 		{
538 		case mDNSAddrType_IPv4: return(mDNSBool)(ip->ip.v4.NotAnInteger == AllDNSLinkGroupv4.NotAnInteger);
539 		case mDNSAddrType_IPv6: return(mDNSBool)(ip->ip.v6.l[0] == AllDNSLinkGroupv6.l[0] &&
540 												 ip->ip.v6.l[1] == AllDNSLinkGroupv6.l[1] &&
541 												 ip->ip.v6.l[2] == AllDNSLinkGroupv6.l[2] &&
542 												 ip->ip.v6.l[3] == AllDNSLinkGroupv6.l[3] );
543 		default: return(mDNSfalse);
544 		}
545 	}
546 
547 // ***************************************************************************
548 #if COMPILER_LIKES_PRAGMA_MARK
549 #pragma mark -
550 #pragma mark - Domain Name Utility Functions
551 #endif
552 
553 mDNSexport mDNSBool SameDomainLabel(const mDNSu8 *a, const mDNSu8 *b)
554 	{
555 	int i;
556 	const int len = *a++;
557 
558 	if (len > MAX_DOMAIN_LABEL)
559 		{ debugf("Malformed label (too long)"); return(mDNSfalse); }
560 
561 	if (len != *b++) return(mDNSfalse);
562 	for (i=0; i<len; i++)
563 		{
564 		mDNSu8 ac = *a++;
565 		mDNSu8 bc = *b++;
566 		if (mDNSIsUpperCase(ac)) ac += 'a' - 'A';
567 		if (mDNSIsUpperCase(bc)) bc += 'a' - 'A';
568 		if (ac != bc) return(mDNSfalse);
569 		}
570 	return(mDNStrue);
571 	}
572 
573 mDNSexport mDNSBool SameDomainName(const domainname *const d1, const domainname *const d2)
574 	{
575 	const mDNSu8 *      a   = d1->c;
576 	const mDNSu8 *      b   = d2->c;
577 	const mDNSu8 *const max = d1->c + MAX_DOMAIN_NAME;			// Maximum that's valid
578 
579 	while (*a || *b)
580 		{
581 		if (a + 1 + *a >= max)
582 			{ debugf("Malformed domain name (more than 255 characters)"); return(mDNSfalse); }
583 		if (!SameDomainLabel(a, b)) return(mDNSfalse);
584 		a += 1 + *a;
585 		b += 1 + *b;
586 		}
587 
588 	return(mDNStrue);
589 	}
590 
591 mDNSexport mDNSBool IsLocalDomain(const domainname *d)
592 	{
593 	// Domains that are defined to be resolved via link-local multicast are:
594 	// local., 254.169.in-addr.arpa., and {8,9,A,B}.E.F.ip6.arpa.
595 	static const domainname *nL = (domainname*)"\x5" "local";
596 	static const domainname *nR = (domainname*)"\x3" "254" "\x3" "169"         "\x7" "in-addr" "\x4" "arpa";
597 	static const domainname *n8 = (domainname*)"\x1" "8"   "\x1" "e" "\x1" "f" "\x3" "ip6"     "\x4" "arpa";
598 	static const domainname *n9 = (domainname*)"\x1" "9"   "\x1" "e" "\x1" "f" "\x3" "ip6"     "\x4" "arpa";
599 	static const domainname *nA = (domainname*)"\x1" "a"   "\x1" "e" "\x1" "f" "\x3" "ip6"     "\x4" "arpa";
600 	static const domainname *nB = (domainname*)"\x1" "b"   "\x1" "e" "\x1" "f" "\x3" "ip6"     "\x4" "arpa";
601 
602 	const domainname *d1, *d2, *d3, *d4, *d5, *d6;	// Top-level domain, second-level domain, etc.
603 	d1 = d2 = d3 = d4 = d5 = d6 = mDNSNULL;
604 	while (d->c[0])
605 		{
606 		d6 = d5; d5 = d4; d4 = d3; d3 = d2; d2 = d1; d1 = d;
607 		d = (domainname*)(d->c + 1 + d->c[0]);
608 		}
609 
610 	if (d1 && SameDomainName(d1, nL)) return(mDNStrue);
611 	if (d4 && SameDomainName(d4, nR)) return(mDNStrue);
612 	if (d6 && SameDomainName(d6, n8)) return(mDNStrue);
613 	if (d6 && SameDomainName(d6, n9)) return(mDNStrue);
614 	if (d6 && SameDomainName(d6, nA)) return(mDNStrue);
615 	if (d6 && SameDomainName(d6, nB)) return(mDNStrue);
616 	return(mDNSfalse);
617 	}
618 
619 // Returns length of a domain name INCLUDING the byte for the final null label
620 // i.e. for the root label "." it returns one
621 // For the FQDN "com." it returns 5 (length byte, three data bytes, final zero)
622 // Legal results are 1 (just root label) to 255 (MAX_DOMAIN_NAME)
623 // If the given domainname is invalid, result is 256
624 mDNSexport mDNSu16 DomainNameLength(const domainname *const name)
625 	{
626 	const mDNSu8 *src = name->c;
627 	while (*src)
628 		{
629 		if (*src > MAX_DOMAIN_LABEL) return(MAX_DOMAIN_NAME+1);
630 		src += 1 + *src;
631 		if (src - name->c >= MAX_DOMAIN_NAME) return(MAX_DOMAIN_NAME+1);
632 		}
633 	return((mDNSu16)(src - name->c + 1));
634 	}
635 
636 // CompressedDomainNameLength returns the length of a domain name INCLUDING the byte
637 // for the final null label i.e. for the root label "." it returns one.
638 // E.g. for the FQDN "foo.com." it returns 9
639 // (length, three data bytes, length, three more data bytes, final zero).
640 // In the case where a parent domain name is provided, and the given name is a child
641 // of that parent, CompressedDomainNameLength returns the length of the prefix portion
642 // of the child name, plus TWO bytes for the compression pointer.
643 // E.g. for the name "foo.com." with parent "com.", it returns 6
644 // (length, three data bytes, two-byte compression pointer).
645 mDNSexport mDNSu16 CompressedDomainNameLength(const domainname *const name, const domainname *parent)
646 	{
647 	const mDNSu8 *src = name->c;
648 	if (parent && parent->c[0] == 0) parent = mDNSNULL;
649 	while (*src)
650 		{
651 		if (*src > MAX_DOMAIN_LABEL) return(MAX_DOMAIN_NAME+1);
652 		if (parent && SameDomainName((domainname *)src, parent)) return((mDNSu16)(src - name->c + 2));
653 		src += 1 + *src;
654 		if (src - name->c >= MAX_DOMAIN_NAME) return(MAX_DOMAIN_NAME+1);
655 		}
656 	return((mDNSu16)(src - name->c + 1));
657 	}
658 
659 // AppendLiteralLabelString appends a single label to an existing (possibly empty) domainname.
660 // The C string contains the label as-is, with no escaping, etc.
661 // Any dots in the name are literal dots, not label separators
662 // If successful, AppendLiteralLabelString returns a pointer to the next unused byte
663 // in the domainname bufer (i.e., the next byte after the terminating zero).
664 // If unable to construct a legal domain name (i.e. label more than 63 bytes, or total more than 255 bytes)
665 // AppendLiteralLabelString returns mDNSNULL.
666 mDNSexport mDNSu8 *AppendLiteralLabelString(domainname *const name, const char *cstr)
667 	{
668 	mDNSu8       *      ptr  = name->c + DomainNameLength(name) - 1;	// Find end of current name
669 	const mDNSu8 *const lim1 = name->c + MAX_DOMAIN_NAME - 1;			// Limit of how much we can add (not counting final zero)
670 	const mDNSu8 *const lim2 = ptr + 1 + MAX_DOMAIN_LABEL;
671 	const mDNSu8 *const lim  = (lim1 < lim2) ? lim1 : lim2;
672 	mDNSu8       *lengthbyte = ptr++;									// Record where the length is going to go
673 
674 	while (*cstr && ptr < lim) *ptr++ = (mDNSu8)*cstr++;	// Copy the data
675 	*lengthbyte = (mDNSu8)(ptr - lengthbyte - 1);			// Fill in the length byte
676 	*ptr++ = 0;												// Put the null root label on the end
677 	if (*cstr) return(mDNSNULL);							// Failure: We didn't successfully consume all input
678 	else return(ptr);										// Success: return new value of ptr
679 	}
680 
681 // AppendDNSNameString appends zero or more labels to an existing (possibly empty) domainname.
682 // The C string is in conventional DNS syntax:
683 // Textual labels, escaped as necessary using the usual DNS '\' notation, separated by dots.
684 // If successful, AppendDNSNameString returns a pointer to the next unused byte
685 // in the domainname bufer (i.e., the next byte after the terminating zero).
686 // If unable to construct a legal domain name (i.e. label more than 63 bytes, or total more than 255 bytes)
687 // AppendDNSNameString returns mDNSNULL.
688 mDNSexport mDNSu8 *AppendDNSNameString(domainname *const name, const char *cstring)
689 	{
690 	const char   *cstr      = cstring;
691 	mDNSu8       *      ptr = name->c + DomainNameLength(name) - 1;	// Find end of current name
692 	const mDNSu8 *const lim = name->c + MAX_DOMAIN_NAME - 1;		// Limit of how much we can add (not counting final zero)
693 	while (*cstr && ptr < lim)										// While more characters, and space to put them...
694 		{
695 		mDNSu8 *lengthbyte = ptr++;									// Record where the length is going to go
696 		if (*cstr == '.') { LogMsg("AppendDNSNameString: Illegal empty label in name \"%s\"", cstring); return(mDNSNULL); }
697 		while (*cstr && *cstr != '.' && ptr < lim)					// While we have characters in the label...
698 			{
699 			mDNSu8 c = (mDNSu8)*cstr++;								// Read the character
700 			if (c == '\\')											// If escape character, check next character
701 				{
702 				c = (mDNSu8)*cstr++;								// Assume we'll just take the next character
703 				if (mdnsIsDigit(cstr[-1]) && mdnsIsDigit(cstr[0]) && mdnsIsDigit(cstr[1]))
704 					{												// If three decimal digits,
705 					int v0 = cstr[-1] - '0';						// then interpret as three-digit decimal
706 					int v1 = cstr[ 0] - '0';
707 					int v2 = cstr[ 1] - '0';
708 					int val = v0 * 100 + v1 * 10 + v2;
709 					if (val <= 255) { c = (mDNSu8)val; cstr += 2; }	// If valid three-digit decimal value, use it
710 					}
711 				}
712 			*ptr++ = c;												// Write the character
713 			}
714 		if (*cstr) cstr++;											// Skip over the trailing dot (if present)
715 		if (ptr - lengthbyte - 1 > MAX_DOMAIN_LABEL)				// If illegal label, abort
716 			return(mDNSNULL);
717 		*lengthbyte = (mDNSu8)(ptr - lengthbyte - 1);				// Fill in the length byte
718 		}
719 
720 	*ptr++ = 0;														// Put the null root label on the end
721 	if (*cstr) return(mDNSNULL);									// Failure: We didn't successfully consume all input
722 	else return(ptr);												// Success: return new value of ptr
723 	}
724 
725 // AppendDomainLabel appends a single label to a name.
726 // If successful, AppendDomainLabel returns a pointer to the next unused byte
727 // in the domainname bufer (i.e., the next byte after the terminating zero).
728 // If unable to construct a legal domain name (i.e. label more than 63 bytes, or total more than 255 bytes)
729 // AppendDomainLabel returns mDNSNULL.
730 mDNSexport mDNSu8 *AppendDomainLabel(domainname *const name, const domainlabel *const label)
731 	{
732 	int i;
733 	mDNSu8 *ptr = name->c + DomainNameLength(name) - 1;
734 
735 	// Check label is legal
736 	if (label->c[0] > MAX_DOMAIN_LABEL) return(mDNSNULL);
737 
738 	// Check that ptr + length byte + data bytes + final zero does not exceed our limit
739 	if (ptr + 1 + label->c[0] + 1 > name->c + MAX_DOMAIN_NAME) return(mDNSNULL);
740 
741 	for (i=0; i<=label->c[0]; i++) *ptr++ = label->c[i];	// Copy the label data
742 	*ptr++ = 0;								// Put the null root label on the end
743 	return(ptr);
744 	}
745 
746 mDNSexport mDNSu8 *AppendDomainName(domainname *const name, const domainname *const append)
747 	{
748 	mDNSu8       *      ptr = name->c + DomainNameLength(name) - 1;	// Find end of current name
749 	const mDNSu8 *const lim = name->c + MAX_DOMAIN_NAME - 1;		// Limit of how much we can add (not counting final zero)
750 	const mDNSu8 *      src = append->c;
751 	while(src[0])
752 		{
753 		int i;
754 		if (ptr + 1 + src[0] > lim) return(mDNSNULL);
755 		for (i=0; i<=src[0]; i++) *ptr++ = src[i];
756 		*ptr = 0;	// Put the null root label on the end
757 		src += i;
758 		}
759 	return(ptr);
760 	}
761 
762 // MakeDomainLabelFromLiteralString makes a single domain label from a single literal C string (with no escaping).
763 // If successful, MakeDomainLabelFromLiteralString returns mDNStrue.
764 // If unable to convert the whole string to a legal domain label (i.e. because length is more than 63 bytes) then
765 // MakeDomainLabelFromLiteralString makes a legal domain label from the first 63 bytes of the string and returns mDNSfalse.
766 // In some cases silently truncated oversized names to 63 bytes is acceptable, so the return result may be ignored.
767 // In other cases silent truncation may not be acceptable, so in those cases the calling function needs to check the return result.
768 mDNSexport mDNSBool MakeDomainLabelFromLiteralString(domainlabel *const label, const char *cstr)
769 	{
770 	mDNSu8       *      ptr   = label->c + 1;						// Where we're putting it
771 	const mDNSu8 *const limit = label->c + 1 + MAX_DOMAIN_LABEL;	// The maximum we can put
772 	while (*cstr && ptr < limit) *ptr++ = (mDNSu8)*cstr++;			// Copy the label
773 	label->c[0] = (mDNSu8)(ptr - label->c - 1);						// Set the length byte
774 	return(*cstr == 0);												// Return mDNStrue if we successfully consumed all input
775 	}
776 
777 // MakeDomainNameFromDNSNameString makes a native DNS-format domainname from a C string.
778 // The C string is in conventional DNS syntax:
779 // Textual labels, escaped as necessary using the usual DNS '\' notation, separated by dots.
780 // If successful, MakeDomainNameFromDNSNameString returns a pointer to the next unused byte
781 // in the domainname bufer (i.e., the next byte after the terminating zero).
782 // If unable to construct a legal domain name (i.e. label more than 63 bytes, or total more than 255 bytes)
783 // MakeDomainNameFromDNSNameString returns mDNSNULL.
784 mDNSexport mDNSu8 *MakeDomainNameFromDNSNameString(domainname *const name, const char *cstr)
785 	{
786 	name->c[0] = 0;									// Make an empty domain name
787 	return(AppendDNSNameString(name, cstr));		// And then add this string to it
788 	}
789 
790 mDNSexport char *ConvertDomainLabelToCString_withescape(const domainlabel *const label, char *ptr, char esc)
791 	{
792 	const mDNSu8 *      src = label->c;							// Domain label we're reading
793 	const mDNSu8        len = *src++;							// Read length of this (non-null) label
794 	const mDNSu8 *const end = src + len;						// Work out where the label ends
795 	if (len > MAX_DOMAIN_LABEL) return(mDNSNULL);				// If illegal label, abort
796 	while (src < end)											// While we have characters in the label
797 		{
798 		mDNSu8 c = *src++;
799 		if (esc)
800 			{
801 			if (c == '.' || c == esc)							// If character is a dot or the escape character
802 				*ptr++ = esc;									// Output escape character
803 			else if (c <= ' ')									// If non-printing ascii,
804 				{												// Output decimal escape sequence
805 				*ptr++ = esc;
806 				*ptr++ = (char)  ('0' + (c / 100)     );
807 				*ptr++ = (char)  ('0' + (c /  10) % 10);
808 				c      = (mDNSu8)('0' + (c      ) % 10);
809 				}
810 			}
811 		*ptr++ = (char)c;										// Copy the character
812 		}
813 	*ptr = 0;													// Null-terminate the string
814 	return(ptr);												// and return
815 	}
816 
817 // Note: To guarantee that there will be no possible overrun, cstr must be at least MAX_ESCAPED_DOMAIN_NAME (1005 bytes)
818 mDNSexport char *ConvertDomainNameToCString_withescape(const domainname *const name, char *ptr, char esc)
819 	{
820 	const mDNSu8 *src         = name->c;								// Domain name we're reading
821 	const mDNSu8 *const max   = name->c + MAX_DOMAIN_NAME;			// Maximum that's valid
822 
823 	if (*src == 0) *ptr++ = '.';									// Special case: For root, just write a dot
824 
825 	while (*src)													// While more characters in the domain name
826 		{
827 		if (src + 1 + *src >= max) return(mDNSNULL);
828 		ptr = ConvertDomainLabelToCString_withescape((const domainlabel *)src, ptr, esc);
829 		if (!ptr) return(mDNSNULL);
830 		src += 1 + *src;
831 		*ptr++ = '.';												// Write the dot after the label
832 		}
833 
834 	*ptr++ = 0;														// Null-terminate the string
835 	return(ptr);													// and return
836 	}
837 
838 // RFC 1034 rules:
839 // Host names must start with a letter, end with a letter or digit,
840 // and have as interior characters only letters, digits, and hyphen.
841 // This was subsequently modified in RFC 1123 to allow the first character to be either a letter or a digit
842 
843 mDNSexport void ConvertUTF8PstringToRFC1034HostLabel(const mDNSu8 UTF8Name[], domainlabel *const hostlabel)
844 	{
845 	const mDNSu8 *      src  = &UTF8Name[1];
846 	const mDNSu8 *const end  = &UTF8Name[1] + UTF8Name[0];
847 	      mDNSu8 *      ptr  = &hostlabel->c[1];
848 	const mDNSu8 *const lim  = &hostlabel->c[1] + MAX_DOMAIN_LABEL;
849 	while (src < end)
850 		{
851 		// Delete apostrophes from source name
852 		if (src[0] == '\'') { src++; continue; }		// Standard straight single quote
853 		if (src + 2 < end && src[0] == 0xE2 && src[1] == 0x80 && src[2] == 0x99)
854 			{ src += 3; continue; }	// Unicode curly apostrophe
855 		if (ptr < lim)
856 			{
857 			if (mdnsValidHostChar(*src, (ptr > &hostlabel->c[1]), (src < end-1))) *ptr++ = *src;
858 			else if (ptr > &hostlabel->c[1] && ptr[-1] != '-') *ptr++ = '-';
859 			}
860 		src++;
861 		}
862 	while (ptr > &hostlabel->c[1] && ptr[-1] == '-') ptr--;	// Truncate trailing '-' marks
863 	hostlabel->c[0] = (mDNSu8)(ptr - &hostlabel->c[1]);
864 	}
865 
866 mDNSexport mDNSu8 *ConstructServiceName(domainname *const fqdn,
867 	const domainlabel *name, const domainname *type, const domainname *const domain)
868 	{
869 	int i, len;
870 	mDNSu8 *dst = fqdn->c;
871 	const mDNSu8 *src;
872 	const char *errormsg;
873 
874 	// In the case where there is no name (and ONLY in that case),
875 	// a single-label subtype is allowed as the first label of a three-part "type"
876 	if (!name && type)
877 		{
878 		const mDNSu8 *s0 = type->c;
879 		if (s0[0] && s0[0] < 0x40)		// If legal first label (at least one character, and no more than 63)
880 			{
881 			const mDNSu8 * s1 = s0 + 1 + s0[0];
882 			if (s1[0] && s1[0] < 0x40)	// and legal second label (at least one character, and no more than 63)
883 				{
884 				const mDNSu8 *s2 = s1 + 1 + s1[0];
885 				if (s2[0] && s2[0] < 0x40 && s2[1+s2[0]] == 0)	// and we have three and only three labels
886 					{
887 					static const mDNSu8 SubTypeLabel[5] = "\x04_sub";
888 					src = s0;									// Copy the first label
889 					len = *src;
890 					for (i=0; i <= len;                      i++) *dst++ = *src++;
891 					for (i=0; i < (int)sizeof(SubTypeLabel); i++) *dst++ = SubTypeLabel[i];
892 					type = (domainname *)s1;
893 
894 					// Special support for queries done by some third-party network monitoring software
895 					// For these queries, we retract the "._sub" we just added between the subtype and the main type
896 					if (SameDomainName((domainname*)s0, (domainname*)"\x09_services\x07_dns-sd\x04_udp") ||
897 						SameDomainName((domainname*)s0, (domainname*)"\x09_services\x05_mdns\x04_udp"))
898 						dst -= sizeof(SubTypeLabel);
899 					}
900 				}
901 			}
902 		}
903 
904 	if (name && name->c[0])
905 		{
906 		src = name->c;									// Put the service name into the domain name
907 		len = *src;
908 		if (len >= 0x40) { errormsg="Service instance name too long"; goto fail; }
909 		for (i=0; i<=len; i++) *dst++ = *src++;
910 		}
911 	else
912 		name = (domainlabel*)"";	// Set this up to be non-null, to avoid errors if we have to call LogMsg() below
913 
914 	src = type->c;										// Put the service type into the domain name
915 	len = *src;
916 	if (len < 2 || len >= 0x40 || (len > 15 && !SameDomainName(domain, &localdomain)))
917 		{
918 		errormsg="Application protocol name must be underscore plus 1-14 characters. See <http://www.dns-sd.org/ServiceTypes.html>";
919 		goto fail;
920 		}
921 	if (src[1] != '_') { errormsg="Application protocol name must begin with underscore"; goto fail; }
922 	for (i=2; i<=len; i++)
923 		if (!mdnsIsLetter(src[i]) && !mdnsIsDigit(src[i]) && src[i] != '-' && src[i] != '_')
924 			{ errormsg="Application protocol name must contain only letters, digits, and hyphens"; goto fail; }
925 	for (i=0; i<=len; i++) *dst++ = *src++;
926 
927 	len = *src;
928 	if (!(len == 4 && src[1] == '_' &&
929 		(((src[2] | 0x20) == 'u' && (src[3] | 0x20) == 'd') || ((src[2] | 0x20) == 't' && (src[3] | 0x20) == 'c')) &&
930 		(src[4] | 0x20) == 'p'))
931 		{ errormsg="Transport protocol name must be _udp or _tcp"; goto fail; }
932 	for (i=0; i<=len; i++) *dst++ = *src++;
933 
934 	if (*src) { errormsg="Service type must have only two labels"; goto fail; }
935 
936 	*dst = 0;
937 	if (!domain->c[0]) { errormsg="Service domain must be non-empty"; goto fail; }
938 	if (SameDomainName(domain, (domainname*)"\x05" "local" "\x04" "arpa"))
939 		{ errormsg="Illegal domain \"local.arpa.\" Use \"local.\" (or empty string)"; goto fail; }
940 	dst = AppendDomainName(fqdn, domain);
941 	if (!dst) { errormsg="Service domain too long"; goto fail; }
942 	return(dst);
943 
944 fail:
945 	LogMsg("ConstructServiceName: %s: %#s.%##s%##s", errormsg, name->c, type->c, domain->c);
946 	return(mDNSNULL);
947 	}
948 
949 // A service name has the form: instance.application-protocol.transport-protocol.domain
950 // DeconstructServiceName is currently fairly forgiving: It doesn't try to enforce character
951 // set or length limits for the protocol names, and the final domain is allowed to be empty.
952 // However, if the given FQDN doesn't contain at least three labels,
953 // DeconstructServiceName will reject it and return mDNSfalse.
954 mDNSexport mDNSBool DeconstructServiceName(const domainname *const fqdn,
955 	domainlabel *const name, domainname *const type, domainname *const domain)
956 	{
957 	int i, len;
958 	const mDNSu8 *src = fqdn->c;
959 	const mDNSu8 *max = fqdn->c + MAX_DOMAIN_NAME;
960 	mDNSu8 *dst;
961 
962 	dst = name->c;										// Extract the service name
963 	len = *src;
964 	if (!len)        { debugf("DeconstructServiceName: FQDN empty!");            return(mDNSfalse); }
965 	if (len >= 0x40) { debugf("DeconstructServiceName: Instance name too long"); return(mDNSfalse); }
966 	for (i=0; i<=len; i++) *dst++ = *src++;
967 
968 	dst = type->c;										// Extract the service type
969 	len = *src;
970 	if (!len)        { debugf("DeconstructServiceName: FQDN contains only one label!");      return(mDNSfalse); }
971 	if (len >= 0x40) { debugf("DeconstructServiceName: Application protocol name too long"); return(mDNSfalse); }
972 	for (i=0; i<=len; i++) *dst++ = *src++;
973 
974 	len = *src;
975 	if (!len)        { debugf("DeconstructServiceName: FQDN contains only two labels!");   return(mDNSfalse); }
976 	if (len >= 0x40) { debugf("DeconstructServiceName: Transport protocol name too long"); return(mDNSfalse); }
977 	for (i=0; i<=len; i++) *dst++ = *src++;
978 	*dst++ = 0;											// Put terminator on the end of service type
979 
980 	dst = domain->c;									// Extract the service domain
981 	while (*src)
982 		{
983 		len = *src;
984 		if (len >= 0x40)
985 			{ debugf("DeconstructServiceName: Label in service domain too long"); return(mDNSfalse); }
986 		if (src + 1 + len + 1 >= max)
987 			{ debugf("DeconstructServiceName: Total service domain too long"); return(mDNSfalse); }
988 		for (i=0; i<=len; i++) *dst++ = *src++;
989 		}
990 	*dst++ = 0;		// Put the null root label on the end
991 
992 	return(mDNStrue);
993 	}
994 
995 // Notes on UTF-8:
996 // 0xxxxxxx represents a 7-bit ASCII value from 0x00 to 0x7F
997 // 10xxxxxx is a continuation byte of a multi-byte character
998 // 110xxxxx is the first byte of a 2-byte character (11 effective bits; values 0x     80 - 0x     800-1)
999 // 1110xxxx is the first byte of a 3-byte character (16 effective bits; values 0x    800 - 0x   10000-1)
1000 // 11110xxx is the first byte of a 4-byte character (21 effective bits; values 0x  10000 - 0x  200000-1)
1001 // 111110xx is the first byte of a 5-byte character (26 effective bits; values 0x 200000 - 0x 4000000-1)
1002 // 1111110x is the first byte of a 6-byte character (31 effective bits; values 0x4000000 - 0x80000000-1)
1003 //
1004 // UTF-16 surrogate pairs are used in UTF-16 to encode values larger than 0xFFFF.
1005 // Although UTF-16 surrogate pairs are not supposed to appear in legal UTF-8, we want to be defensive
1006 // about that too. (See <http://www.unicode.org/faq/utf_bom.html#34>, "What are surrogates?")
1007 // The first of pair is a UTF-16 value in the range 0xD800-0xDBFF (11101101 1010xxxx 10xxxxxx in UTF-8),
1008 // and the second    is a UTF-16 value in the range 0xDC00-0xDFFF (11101101 1011xxxx 10xxxxxx in UTF-8).
1009 
1010 mDNSexport mDNSu32 TruncateUTF8ToLength(mDNSu8 *string, mDNSu32 length, mDNSu32 max)
1011 	{
1012 	if (length > max)
1013 		{
1014 		mDNSu8 c1 = string[max];								// First byte after cut point
1015 		mDNSu8 c2 = (max+1 < length) ? string[max+1] : 0xB0;	// Second byte after cut point
1016 		length = max;	// Trim length down
1017 		while (length > 0)
1018 			{
1019 			// Check if the byte right after the chop point is a UTF-8 continuation byte,
1020 			// or if the character right after the chop point is the second of a UTF-16 surrogate pair.
1021 			// If so, then we continue to chop more bytes until we get to a legal chop point.
1022 			mDNSBool continuation    = ((c1 & 0xC0) == 0x80);
1023 			mDNSBool secondsurrogate = (c1 == 0xED && (c2 & 0xF0) == 0xB0);
1024 			if (!continuation && !secondsurrogate) break;
1025 			c2 = c1;
1026 			c1 = string[--length];
1027 			}
1028 		// Having truncated characters off the end of our string, also cut off any residual white space
1029 		while (length > 0 && string[length-1] <= ' ') length--;
1030 		}
1031 	return(length);
1032 	}
1033 
1034 // Returns true if a rich text label ends in " (nnn)", or if an RFC 1034
1035 // name ends in "-nnn", where n is some decimal number.
1036 mDNSexport mDNSBool LabelContainsSuffix(const domainlabel *const name, const mDNSBool RichText)
1037 	{
1038 	mDNSu16 l = name->c[0];
1039 
1040 	if (RichText)
1041 		{
1042 		if (l < 4) return mDNSfalse;							// Need at least " (2)"
1043 		if (name->c[l--] != ')') return mDNSfalse;				// Last char must be ')'
1044 		if (!mdnsIsDigit(name->c[l])) return mDNSfalse;			// Preceeded by a digit
1045 		l--;
1046 		while (l > 2 && mdnsIsDigit(name->c[l])) l--;			// Strip off digits
1047 		return (name->c[l] == '(' && name->c[l - 1] == ' ');
1048 		}
1049 	else
1050 		{
1051 		if (l < 2) return mDNSfalse;							// Need at least "-2"
1052 		if (!mdnsIsDigit(name->c[l])) return mDNSfalse;			// Last char must be a digit
1053 		l--;
1054 		while (l > 2 && mdnsIsDigit(name->c[l])) l--;			// Strip off digits
1055 		return (name->c[l] == '-');
1056 		}
1057 	}
1058 
1059 // removes an auto-generated suffix (appended on a name collision) from a label.  caller is
1060 // responsible for ensuring that the label does indeed contain a suffix.  returns the number
1061 // from the suffix that was removed.
1062 mDNSexport mDNSu32 RemoveLabelSuffix(domainlabel *name, mDNSBool RichText)
1063 	{
1064 	mDNSu32 val = 0, multiplier = 1;
1065 
1066 	// Chop closing parentheses from RichText suffix
1067 	if (RichText && name->c[0] >= 1 && name->c[name->c[0]] == ')') name->c[0]--;
1068 
1069 	// Get any existing numerical suffix off the name
1070 	while (mdnsIsDigit(name->c[name->c[0]]))
1071 		{ val += (name->c[name->c[0]] - '0') * multiplier; multiplier *= 10; name->c[0]--; }
1072 
1073 	// Chop opening parentheses or dash from suffix
1074 	if (RichText)
1075 		{
1076 		if (name->c[0] >= 2 && name->c[name->c[0]] == '(' && name->c[name->c[0]-1] == ' ') name->c[0] -= 2;
1077 		}
1078 	else
1079 		{
1080 		if (name->c[0] >= 1 && name->c[name->c[0]] == '-') name->c[0] -= 1;
1081 		}
1082 
1083 	return(val);
1084 	}
1085 
1086 // appends a numerical suffix to a label, with the number following a whitespace and enclosed
1087 // in parentheses (rich text) or following two consecutive hyphens (RFC 1034 domain label).
1088 mDNSexport void AppendLabelSuffix(domainlabel *name, mDNSu32 val, mDNSBool RichText)
1089 	{
1090 	mDNSu32 divisor = 1, chars = 2;	// Shortest possible RFC1034 name suffix is 2 characters ("-2")
1091 	if (RichText) chars = 4;		// Shortest possible RichText suffix is 4 characters (" (2)")
1092 
1093 	// Truncate trailing spaces from RichText names
1094 	if (RichText) while (name->c[name->c[0]] == ' ') name->c[0]--;
1095 
1096 	while (val >= divisor * 10) { divisor *= 10; chars++; }
1097 
1098 	name->c[0] = (mDNSu8) TruncateUTF8ToLength(name->c+1, name->c[0], MAX_DOMAIN_LABEL - chars);
1099 
1100 	if (RichText) { name->c[++name->c[0]] = ' '; name->c[++name->c[0]] = '('; }
1101 	else          { name->c[++name->c[0]] = '-'; }
1102 
1103 	while (divisor)
1104 		{
1105 		name->c[++name->c[0]] = (mDNSu8)('0' + val / divisor);
1106 		val     %= divisor;
1107 		divisor /= 10;
1108 		}
1109 
1110 	if (RichText) name->c[++name->c[0]] = ')';
1111 	}
1112 
1113 mDNSexport void IncrementLabelSuffix(domainlabel *name, mDNSBool RichText)
1114 	{
1115 	mDNSu32 val = 0;
1116 
1117 	if (LabelContainsSuffix(name, RichText))
1118 		val = RemoveLabelSuffix(name, RichText);
1119 
1120 	// If no existing suffix, start by renaming "Foo" as "Foo (2)" or "Foo-2" as appropriate.
1121 	// If existing suffix in the range 2-9, increment it.
1122 	// If we've had ten conflicts already, there are probably too many hosts trying to use the same name,
1123 	// so add a random increment to improve the chances of finding an available name next time.
1124 	if      (val == 0) val = 2;
1125 	else if (val < 10) val++;
1126 	else               val += 1 + mDNSRandom(99);
1127 
1128 	AppendLabelSuffix(name, val, RichText);
1129 	}
1130 
1131 // ***************************************************************************
1132 #if COMPILER_LIKES_PRAGMA_MARK
1133 #pragma mark -
1134 #pragma mark - Resource Record Utility Functions
1135 #endif
1136 
1137 mDNSexport mDNSu32 RDataHashValue(mDNSu16 const rdlength, const RDataBody *const rdb)
1138 	{
1139 	mDNSu32 sum = 0;
1140 	int i;
1141 	for (i=0; i+1 < rdlength; i+=2)
1142 		{
1143 		sum += (((mDNSu32)(rdb->data[i])) << 8) | rdb->data[i+1];
1144 		sum = (sum<<3) | (sum>>29);
1145 		}
1146 	if (i < rdlength)
1147 		{
1148 		sum += ((mDNSu32)(rdb->data[i])) << 8;
1149 		}
1150 	return(sum);
1151 	}
1152 
1153 // r1 has to be a full ResourceRecord including rrtype and rdlength
1154 // r2 is just a bare RDataBody, which MUST be the same rrtype and rdlength as r1
1155 mDNSexport mDNSBool SameRDataBody(const ResourceRecord *const r1, const RDataBody *const r2)
1156 	{
1157 	switch(r1->rrtype)
1158 		{
1159 		case kDNSType_CNAME:// Same as PTR
1160 		case kDNSType_PTR:	return(SameDomainName(&r1->rdata->u.name, &r2->name));
1161 
1162 		case kDNSType_SRV:	return(mDNSBool)(  	r1->rdata->u.srv.priority          == r2->srv.priority          &&
1163 												r1->rdata->u.srv.weight            == r2->srv.weight            &&
1164 												r1->rdata->u.srv.port.NotAnInteger == r2->srv.port.NotAnInteger &&
1165 												SameDomainName(&r1->rdata->u.srv.target, &r2->srv.target)       );
1166 
1167 		default:			return(mDNSPlatformMemSame(r1->rdata->u.data, r2->data, r1->rdlength));
1168 		}
1169 	}
1170 
1171 mDNSexport mDNSBool SameRData(const ResourceRecord *const r1, const ResourceRecord *const r2)
1172 	{
1173 	if (r1->rrtype     != r2->rrtype)     return(mDNSfalse);
1174 	if (r1->rdlength   != r2->rdlength)   return(mDNSfalse);
1175 	if (r1->rdatahash  != r2->rdatahash)  return(mDNSfalse);
1176 	return(SameRDataBody(r1, &r2->rdata->u));
1177 	}
1178 
1179 mDNSexport mDNSBool SameResourceRecord(ResourceRecord *r1, ResourceRecord *r2)
1180 	{
1181 	return (r1->namehash == r2->namehash &&
1182 			r1->rrtype == r2->rrtype &&
1183 			SameDomainName(r1->name, r2->name) &&
1184 			SameRData(r1, r2));
1185 	}
1186 
1187 mDNSexport mDNSBool ResourceRecordAnswersQuestion(const ResourceRecord *const rr, const DNSQuestion *const q)
1188 	{
1189 	if (rr->InterfaceID &&
1190 		q ->InterfaceID && q->InterfaceID != mDNSInterface_LocalOnly &&
1191 		rr->InterfaceID != q->InterfaceID) return(mDNSfalse);
1192 
1193 	// RR type CNAME matches any query type. QTYPE ANY matches any RR type. QCLASS ANY matches any RR class.
1194 	if (rr->rrtype != kDNSType_CNAME && rr->rrtype  != q->qtype  && q->qtype  != kDNSQType_ANY ) return(mDNSfalse);
1195 	if (                                rr->rrclass != q->qclass && q->qclass != kDNSQClass_ANY) return(mDNSfalse);
1196 	return(rr->namehash == q->qnamehash && SameDomainName(rr->name, &q->qname));
1197 	}
1198 
1199 mDNSexport mDNSu16 GetRDLength(const ResourceRecord *const rr, mDNSBool estimate)
1200 	{
1201 	const RDataBody *rd = &rr->rdata->u;
1202 	const domainname *const name = estimate ? rr->name : mDNSNULL;
1203 	switch (rr->rrtype)
1204 		{
1205 		case kDNSType_A:	return(sizeof(rd->ipv4));
1206 		case kDNSType_CNAME:// Same as PTR
1207 		case kDNSType_NS:   // Same as PTR
1208 		case kDNSType_PTR:	return(CompressedDomainNameLength(&rd->name, name));
1209 		case kDNSType_HINFO:return(mDNSu16)(2 + (int)rd->data[0] + (int)rd->data[1 + (int)rd->data[0]]);
1210 		case kDNSType_NULL:	// Same as TXT -- not self-describing, so have to just trust rdlength
1211 		case kDNSType_TXT:  return(rr->rdlength); // TXT is not self-describing, so have to just trust rdlength
1212 		case kDNSType_AAAA:	return(sizeof(rd->ipv6));
1213 		case kDNSType_SRV:	return(mDNSu16)(6 + CompressedDomainNameLength(&rd->srv.target, name));
1214 		case kDNSType_SOA:  return (mDNSu16)(CompressedDomainNameLength(&rd->soa.mname, name) +
1215 											CompressedDomainNameLength(&rd->soa.rname, name) +
1216 											5 * sizeof(mDNSOpaque32));
1217 		case kDNSType_OPT:  return(rr->rdlength);
1218 		default:			debugf("Warning! Don't know how to get length of resource type %d", rr->rrtype);
1219 							return(rr->rdlength);
1220 		}
1221 	}
1222 
1223 mDNSexport mDNSBool ValidateRData(const mDNSu16 rrtype, const mDNSu16 rdlength, const RData *const rd)
1224 	{
1225 	mDNSu16 len;
1226 
1227 	switch(rrtype)
1228 		{
1229 		case kDNSType_A:	return(rdlength == sizeof(mDNSv4Addr));
1230 
1231 		case kDNSType_NS:	// Same as PTR
1232 		case kDNSType_MD:	// Same as PTR
1233 		case kDNSType_MF:	// Same as PTR
1234 		case kDNSType_CNAME:// Same as PTR
1235 		//case kDNSType_SOA not checked
1236 		case kDNSType_MB:	// Same as PTR
1237 		case kDNSType_MG:	// Same as PTR
1238 		case kDNSType_MR:	// Same as PTR
1239 		//case kDNSType_NULL not checked (no specified format, so always valid)
1240 		//case kDNSType_WKS not checked
1241 		case kDNSType_PTR:	if (!rdlength) return(mDNSfalse);
1242 							len = DomainNameLength(&rd->u.name);
1243 							return(len <= MAX_DOMAIN_NAME && rdlength == len);
1244 
1245 		case kDNSType_HINFO:// Same as TXT (roughly)
1246 		case kDNSType_MINFO:// Same as TXT (roughly)
1247 		case kDNSType_TXT:  if (!rdlength) return(mDNSfalse); // TXT record has to be at least one byte (RFC 1035)
1248 							{
1249 							const mDNSu8 *ptr = rd->u.txt.c;
1250 							const mDNSu8 *end = rd->u.txt.c + rdlength;
1251 							while (ptr < end) ptr += 1 + ptr[0];
1252 							return (ptr == end);
1253 							}
1254 
1255 		case kDNSType_AAAA:	return(rdlength == sizeof(mDNSv6Addr));
1256 
1257 		case kDNSType_MX:   if (!rdlength) return(mDNSfalse);
1258 							len = DomainNameLength(&rd->u.mx.exchange);
1259 							return(len <= MAX_DOMAIN_NAME && rdlength == 2+len);
1260 
1261 		case kDNSType_SRV:	if (!rdlength) return(mDNSfalse);
1262 							len = DomainNameLength(&rd->u.srv.target);
1263 							return(len <= MAX_DOMAIN_NAME && rdlength == 6+len);
1264 
1265 		default:			return(mDNStrue);	// Allow all other types without checking
1266 		}
1267 	}
1268 
1269 // ***************************************************************************
1270 #if COMPILER_LIKES_PRAGMA_MARK
1271 #pragma mark -
1272 #pragma mark -
1273 #pragma mark - DNS Message Creation Functions
1274 #endif
1275 
1276 mDNSexport void InitializeDNSMessage(DNSMessageHeader *h, mDNSOpaque16 id, mDNSOpaque16 flags)
1277 	{
1278 	h->id             = id;
1279 	h->flags          = flags;
1280 	h->numQuestions   = 0;
1281 	h->numAnswers     = 0;
1282 	h->numAuthorities = 0;
1283 	h->numAdditionals = 0;
1284 	}
1285 
1286 mDNSexport const mDNSu8 *FindCompressionPointer(const mDNSu8 *const base, const mDNSu8 *const end, const mDNSu8 *const domname)
1287 	{
1288 	const mDNSu8 *result = end - *domname - 1;
1289 
1290 	if (*domname == 0) return(mDNSNULL);	// There's no point trying to match just the root label
1291 
1292 	// This loop examines each possible starting position in packet, starting end of the packet and working backwards
1293 	while (result >= base)
1294 		{
1295 		// If the length byte and first character of the label match, then check further to see
1296 		// if this location in the packet will yield a useful name compression pointer.
1297 		if (result[0] == domname[0] && result[1] == domname[1])
1298 			{
1299 			const mDNSu8 *name = domname;
1300 			const mDNSu8 *targ = result;
1301 			while (targ + *name < end)
1302 				{
1303 				// First see if this label matches
1304 				int i;
1305 				const mDNSu8 *pointertarget;
1306 				for (i=0; i <= *name; i++) if (targ[i] != name[i]) break;
1307 				if (i <= *name) break;							// If label did not match, bail out
1308 				targ += 1 + *name;								// Else, did match, so advance target pointer
1309 				name += 1 + *name;								// and proceed to check next label
1310 				if (*name == 0 && *targ == 0) return(result);	// If no more labels, we found a match!
1311 				if (*name == 0) break;							// If no more labels to match, we failed, so bail out
1312 
1313 				// The label matched, so now follow the pointer (if appropriate) and then see if the next label matches
1314 				if (targ[0] < 0x40) continue;					// If length value, continue to check next label
1315 				if (targ[0] < 0xC0) break;						// If 40-BF, not valid
1316 				if (targ+1 >= end) break;						// Second byte not present!
1317 				pointertarget = base + (((mDNSu16)(targ[0] & 0x3F)) << 8) + targ[1];
1318 				if (targ < pointertarget) break;				// Pointertarget must point *backwards* in the packet
1319 				if (pointertarget[0] >= 0x40) break;			// Pointertarget must point to a valid length byte
1320 				targ = pointertarget;
1321 				}
1322 			}
1323 		result--;	// We failed to match at this search position, so back up the tentative result pointer and try again
1324 		}
1325 	return(mDNSNULL);
1326 	}
1327 
1328 // Put a string of dot-separated labels as length-prefixed labels
1329 // domainname is a fully-qualified name (i.e. assumed to be ending in a dot, even if it doesn't)
1330 // msg points to the message we're building (pass mDNSNULL if we don't want to use compression pointers)
1331 // end points to the end of the message so far
1332 // ptr points to where we want to put the name
1333 // limit points to one byte past the end of the buffer that we must not overrun
1334 // domainname is the name to put
1335 mDNSexport mDNSu8 *putDomainNameAsLabels(const DNSMessage *const msg,
1336 	mDNSu8 *ptr, const mDNSu8 *const limit, const domainname *const name)
1337 	{
1338 	const mDNSu8 *const base        = (const mDNSu8 *)msg;
1339 	const mDNSu8 *      np          = name->c;
1340 	const mDNSu8 *const max         = name->c + MAX_DOMAIN_NAME;	// Maximum that's valid
1341 	const mDNSu8 *      pointer     = mDNSNULL;
1342 	const mDNSu8 *const searchlimit = ptr;
1343 
1344 	while (*np && ptr < limit-1)		// While we've got characters in the name, and space to write them in the message...
1345 		{
1346 		if (*np > MAX_DOMAIN_LABEL)
1347 			{ LogMsg("Malformed domain name %##s (label more than 63 bytes)", name->c); return(mDNSNULL); }
1348 
1349 		// This check correctly allows for the final trailing root label:
1350 		// e.g.
1351 		// Suppose our domain name is exactly 255 bytes long, including the final trailing root label.
1352 		// Suppose np is now at name->c[248], and we're about to write our last non-null label ("local").
1353 		// We know that max will be at name->c[255]
1354 		// That means that np + 1 + 5 == max - 1, so we (just) pass the "if" test below, write our
1355 		// six bytes, then exit the loop, write the final terminating root label, and the domain
1356 		// name we've written is exactly 255 bytes long, exactly at the correct legal limit.
1357 		// If the name is one byte longer, then we fail the "if" test below, and correctly bail out.
1358 		if (np + 1 + *np >= max)
1359 			{ LogMsg("Malformed domain name %##s (more than 255 bytes)", name->c); return(mDNSNULL); }
1360 
1361 		if (base) pointer = FindCompressionPointer(base, searchlimit, np);
1362 		if (pointer)					// Use a compression pointer if we can
1363 			{
1364 			mDNSu16 offset = (mDNSu16)(pointer - base);
1365 			*ptr++ = (mDNSu8)(0xC0 | (offset >> 8));
1366 			*ptr++ = (mDNSu8)(        offset &  0xFF);
1367 			return(ptr);
1368 			}
1369 		else							// Else copy one label and try again
1370 			{
1371 			int i;
1372 			mDNSu8 len = *np++;
1373 			if (ptr + 1 + len >= limit) return(mDNSNULL);
1374 			*ptr++ = len;
1375 			for (i=0; i<len; i++) *ptr++ = *np++;
1376 			}
1377 		}
1378 
1379 	if (ptr < limit)												// If we didn't run out of space
1380 		{
1381 		*ptr++ = 0;													// Put the final root label
1382 		return(ptr);												// and return
1383 		}
1384 
1385 	return(mDNSNULL);
1386 	}
1387 
1388 mDNSlocal mDNSu8 *putVal16(mDNSu8 *ptr, mDNSu16 val)
1389 	{
1390 	ptr[0] = (mDNSu8)((val >> 8 ) & 0xFF);
1391 	ptr[1] = (mDNSu8)((val      ) & 0xFF);
1392 	return ptr + sizeof(mDNSOpaque16);
1393 	}
1394 
1395 mDNSlocal mDNSu8 *putVal32(mDNSu8 *ptr, mDNSu32 val)
1396 	{
1397 	ptr[0] = (mDNSu8)((val >> 24) & 0xFF);
1398 	ptr[1] = (mDNSu8)((val >> 16) & 0xFF);
1399 	ptr[2] = (mDNSu8)((val >>  8) & 0xFF);
1400 	ptr[3] = (mDNSu8)((val      ) & 0xFF);
1401 	return ptr + sizeof(mDNSu32);
1402 	}
1403 
1404 mDNSlocal mDNSu8 *putOptRData(mDNSu8 *ptr, const mDNSu8 *limit, ResourceRecord *rr)
1405 	{
1406 	int nput = 0;
1407 	rdataOpt *opt;
1408 
1409 	while (nput < rr->rdlength)
1410 		{
1411 		// check if space for opt/optlen
1412 		if (ptr + (2 * sizeof(mDNSu16)) > limit) goto space_err;
1413 		opt = (rdataOpt *)(rr->rdata->u.data + nput);
1414 		ptr = putVal16(ptr, opt->opt);
1415 		ptr = putVal16(ptr, opt->optlen);
1416 		nput += 2 * sizeof(mDNSu16);
1417 		if (opt->opt == kDNSOpt_LLQ)
1418 			{
1419 			if (ptr + LLQ_OPTLEN > limit) goto space_err;
1420 			ptr = putVal16(ptr, opt->OptData.llq.vers);
1421 			ptr = putVal16(ptr, opt->OptData.llq.llqOp);
1422 			ptr = putVal16(ptr, opt->OptData.llq.err);
1423 			mDNSPlatformMemCopy(opt->OptData.llq.id, ptr, 8);  // 8-byte id
1424 			ptr += 8;
1425 			ptr = putVal32(ptr, opt->OptData.llq.lease);
1426 			nput += LLQ_OPTLEN;
1427 			}
1428 		else if (opt->opt == kDNSOpt_Lease)
1429 			{
1430 			if (ptr + sizeof(mDNSs32) > limit) goto space_err;
1431 			ptr = putVal32(ptr, opt->OptData.lease);
1432 			nput += sizeof(mDNSs32);
1433 			}
1434 		else { LogMsg("putOptRData - unknown option %d", opt->opt); return mDNSNULL; }
1435 		}
1436 
1437 	return ptr;
1438 
1439 	space_err:
1440 	LogMsg("ERROR: putOptRData - out of space");
1441 	return mDNSNULL;
1442 	}
1443 
1444 mDNSlocal mDNSu16 getVal16(const mDNSu8 **ptr)
1445 	{
1446 	mDNSu16 val = (mDNSu16)(((mDNSu16)(*ptr)[0]) << 8 | (*ptr)[1]);
1447 	*ptr += sizeof(mDNSOpaque16);
1448 	return val;
1449 	}
1450 
1451 mDNSlocal const mDNSu8 *getOptRdata(const mDNSu8 *ptr, const mDNSu8 *const limit, LargeCacheRecord *const cr, mDNSu16 pktRDLen)
1452 	{
1453 	int nread = 0;
1454 	ResourceRecord *const rr = &cr->r.resrec;
1455 	rdataOpt *opt = (rdataOpt *)rr->rdata->u.data;
1456 
1457 	while (nread < pktRDLen && (mDNSu8 *)opt < rr->rdata->u.data + MaximumRDSize - sizeof(rdataOpt))
1458 		{
1459 		// space for opt + optlen
1460 		if (nread + (2 * sizeof(mDNSu16)) > rr->rdata->MaxRDLength) goto space_err;
1461 		opt->opt = getVal16(&ptr);
1462 		opt->optlen = getVal16(&ptr);
1463 		nread += 2 * sizeof(mDNSu16);
1464 		if (opt->opt == kDNSOpt_LLQ)
1465 			{
1466 			if ((unsigned)(limit - ptr) < LLQ_OPTLEN) goto space_err;
1467 			opt->OptData.llq.vers = getVal16(&ptr);
1468 			opt->OptData.llq.llqOp = getVal16(&ptr);
1469 			opt->OptData.llq.err = getVal16(&ptr);
1470 			mDNSPlatformMemCopy(ptr, opt->OptData.llq.id, 8);
1471 			ptr += 8;
1472 			opt->OptData.llq.lease = (mDNSu32) ((mDNSu32)ptr[0] << 24 | (mDNSu32)ptr[1] << 16 | (mDNSu32)ptr[2] << 8 | ptr[3]);
1473 			if (opt->OptData.llq.lease > 0x70000000UL / mDNSPlatformOneSecond)
1474 				opt->OptData.llq.lease = 0x70000000UL / mDNSPlatformOneSecond;
1475 			ptr += sizeof(mDNSOpaque32);
1476 			nread += LLQ_OPTLEN;
1477 			}
1478 		else if (opt->opt == kDNSOpt_Lease)
1479 			{
1480 			if ((unsigned)(limit - ptr) < sizeof(mDNSs32)) goto space_err;
1481 
1482 			opt->OptData.lease = (mDNSu32) ((mDNSu32)ptr[0] << 24 | (mDNSu32)ptr[1] << 16 | (mDNSu32)ptr[2] << 8 | ptr[3]);
1483 			if (opt->OptData.lease > 0x70000000UL / mDNSPlatformOneSecond)
1484 				opt->OptData.lease = 0x70000000UL / mDNSPlatformOneSecond;
1485 			ptr += sizeof(mDNSs32);
1486 			nread += sizeof(mDNSs32);
1487 			}
1488 		else { LogMsg("ERROR: getOptRdata - unknown opt %d", opt->opt); return mDNSNULL; }
1489 		opt++;  // increment pointer into rdatabody
1490 		}
1491 
1492 	rr->rdlength = pktRDLen;
1493 	return ptr;
1494 
1495 	space_err:
1496 	LogMsg("ERROR: getLLQRdata - out of space");
1497 	return mDNSNULL;
1498 	}
1499 
1500 mDNSexport mDNSu8 *putRData(const DNSMessage *const msg, mDNSu8 *ptr, const mDNSu8 *const limit, ResourceRecord *rr)
1501 	{
1502 	switch (rr->rrtype)
1503 		{
1504 		case kDNSType_A:	if (rr->rdlength != 4)
1505 								{
1506 								debugf("putRData: Illegal length %d for kDNSType_A", rr->rdlength);
1507 								return(mDNSNULL);
1508 								}
1509 							if (ptr + 4 > limit) return(mDNSNULL);
1510 							*ptr++ = rr->rdata->u.ipv4.b[0];
1511 							*ptr++ = rr->rdata->u.ipv4.b[1];
1512 							*ptr++ = rr->rdata->u.ipv4.b[2];
1513 							*ptr++ = rr->rdata->u.ipv4.b[3];
1514 							return(ptr);
1515 
1516 		case kDNSType_CNAME:// Same as PTR
1517 		case kDNSType_PTR:	return(putDomainNameAsLabels(msg, ptr, limit, &rr->rdata->u.name));
1518 
1519 		case kDNSType_AAAA:	if (rr->rdlength != sizeof(rr->rdata->u.ipv6))
1520 								{
1521 								debugf("putRData: Illegal length %d for kDNSType_AAAA", rr->rdlength);
1522 								return(mDNSNULL);
1523 								}
1524 							if (ptr + sizeof(rr->rdata->u.ipv6) > limit) return(mDNSNULL);
1525 							mDNSPlatformMemCopy(&rr->rdata->u.ipv6, ptr, sizeof(rr->rdata->u.ipv6));
1526 							return(ptr + sizeof(rr->rdata->u.ipv6));
1527 
1528 		case kDNSType_SRV:	if (ptr + 6 > limit) return(mDNSNULL);
1529 							*ptr++ = (mDNSu8)(rr->rdata->u.srv.priority >> 8);
1530 							*ptr++ = (mDNSu8)(rr->rdata->u.srv.priority &  0xFF);
1531 							*ptr++ = (mDNSu8)(rr->rdata->u.srv.weight   >> 8);
1532 							*ptr++ = (mDNSu8)(rr->rdata->u.srv.weight   &  0xFF);
1533 							*ptr++ = rr->rdata->u.srv.port.b[0];
1534 							*ptr++ = rr->rdata->u.srv.port.b[1];
1535 							return(putDomainNameAsLabels(msg, ptr, limit, &rr->rdata->u.srv.target));
1536 		case kDNSType_OPT:	return putOptRData(ptr, limit, rr);
1537 
1538 		default:			debugf("putRData: Warning! Writing unknown resource type %d as raw data", rr->rrtype);
1539 							// Fall through to common code below
1540 		case kDNSType_HINFO:
1541 		case kDNSType_TXT:
1542 		case kDNSType_TSIG:	if (ptr + rr->rdlength > limit) return(mDNSNULL);
1543 							mDNSPlatformMemCopy(rr->rdata->u.data, ptr, rr->rdlength);
1544 							return(ptr + rr->rdlength);
1545 		}
1546 	}
1547 
1548 mDNSexport mDNSu8 *PutResourceRecordTTLWithLimit(DNSMessage *const msg, mDNSu8 *ptr, mDNSu16 *count, ResourceRecord *rr, mDNSu32 ttl, const mDNSu8 *limit)
1549 	{
1550 	mDNSu8 *endofrdata;
1551 	mDNSu16 actualLength;
1552 
1553 	if (rr->RecordType == kDNSRecordTypeUnregistered)
1554 		{
1555 		LogMsg("PutResourceRecord ERROR! Attempt to put kDNSRecordTypeUnregistered %##s (%s)", rr->name->c, DNSTypeName(rr->rrtype));
1556 		return(ptr);
1557 		}
1558 
1559 	ptr = putDomainNameAsLabels(msg, ptr, limit, rr->name);
1560 	if (!ptr || ptr + 10 >= limit) return(mDNSNULL);	// If we're out-of-space, return mDNSNULL
1561 	ptr[0] = (mDNSu8)(rr->rrtype  >> 8);
1562 	ptr[1] = (mDNSu8)(rr->rrtype  &  0xFF);
1563 	ptr[2] = (mDNSu8)(rr->rrclass >> 8);
1564 	ptr[3] = (mDNSu8)(rr->rrclass &  0xFF);
1565 	ptr[4] = (mDNSu8)((ttl >> 24) &  0xFF);
1566 	ptr[5] = (mDNSu8)((ttl >> 16) &  0xFF);
1567 	ptr[6] = (mDNSu8)((ttl >>  8) &  0xFF);
1568 	ptr[7] = (mDNSu8)( ttl        &  0xFF);
1569 	endofrdata = putRData(msg, ptr+10, limit, rr);
1570 	if (!endofrdata) { verbosedebugf("Ran out of space in PutResourceRecord for %##s (%s)", rr->name->c, DNSTypeName(rr->rrtype)); return(mDNSNULL); }
1571 
1572 	// Go back and fill in the actual number of data bytes we wrote
1573 	// (actualLength can be less than rdlength when domain name compression is used)
1574 	actualLength = (mDNSu16)(endofrdata - ptr - 10);
1575 	ptr[8] = (mDNSu8)(actualLength >> 8);
1576 	ptr[9] = (mDNSu8)(actualLength &  0xFF);
1577 
1578 	if (count) (*count)++;
1579 	else LogMsg("PutResourceRecordTTL: ERROR: No target count to update for %##s (%s)", rr->name->c, DNSTypeName(rr->rrtype));
1580 	return(endofrdata);
1581 	}
1582 
1583 mDNSexport mDNSu8 *PutResourceRecordCappedTTL(DNSMessage *const msg, mDNSu8 *ptr, mDNSu16 *count, ResourceRecord *rr, mDNSu32
1584 											   maxttl)
1585 	{
1586 	if (maxttl > rr->rroriginalttl) maxttl = rr->rroriginalttl;
1587 	return(PutResourceRecordTTL(msg, ptr, count, rr, maxttl));
1588 	}
1589 
1590 mDNSexport mDNSu8 *putEmptyResourceRecord(DNSMessage *const msg, mDNSu8 *ptr, const mDNSu8 *const limit,
1591 	mDNSu16 *count, const AuthRecord *rr)
1592 	{
1593 	ptr = putDomainNameAsLabels(msg, ptr, limit, rr->resrec.name);
1594 	if (!ptr || ptr + 10 > limit) return(mDNSNULL);		// If we're out-of-space, return mDNSNULL
1595 	ptr[0] = (mDNSu8)(rr->resrec.rrtype  >> 8);				// Put type
1596 	ptr[1] = (mDNSu8)(rr->resrec.rrtype  &  0xFF);
1597 	ptr[2] = (mDNSu8)(rr->resrec.rrclass >> 8);				// Put class
1598 	ptr[3] = (mDNSu8)(rr->resrec.rrclass &  0xFF);
1599 	ptr[4] = ptr[5] = ptr[6] = ptr[7] = 0;				// TTL is zero
1600 	ptr[8] = ptr[9] = 0;								// RDATA length is zero
1601 	(*count)++;
1602 	return(ptr + 10);
1603 	}
1604 
1605 mDNSexport mDNSu8 *putQuestion(DNSMessage *const msg, mDNSu8 *ptr, const mDNSu8 *const limit, const domainname *const name, mDNSu16 rrtype, mDNSu16 rrclass)
1606 	{
1607 	ptr = putDomainNameAsLabels(msg, ptr, limit, name);
1608 	if (!ptr || ptr+4 >= limit) return(mDNSNULL);			// If we're out-of-space, return mDNSNULL
1609 	ptr[0] = (mDNSu8)(rrtype  >> 8);
1610 	ptr[1] = (mDNSu8)(rrtype  &  0xFF);
1611 	ptr[2] = (mDNSu8)(rrclass >> 8);
1612 	ptr[3] = (mDNSu8)(rrclass &  0xFF);
1613 	msg->h.numQuestions++;
1614 	return(ptr+4);
1615 	}
1616 
1617 // for dynamic updates
1618 mDNSexport mDNSu8 *putZone(DNSMessage *const msg, mDNSu8 *ptr, mDNSu8 *limit, const domainname *zone, mDNSOpaque16 zoneClass)
1619 	{
1620 	ptr = putDomainNameAsLabels(msg, ptr, limit, zone);
1621 	if (!ptr || ptr + 4 > limit) return mDNSNULL;		// If we're out-of-space, return NULL
1622 	*ptr++ = (mDNSu8)(kDNSType_SOA  >> 8);
1623 	*ptr++ = (mDNSu8)(kDNSType_SOA  &  0xFF);
1624 	*ptr++ = zoneClass.b[0];
1625 	*ptr++ = zoneClass.b[1];
1626 	msg->h.mDNS_numZones++;
1627 	return ptr;
1628 	}
1629 
1630 // for dynamic updates
1631 mDNSexport mDNSu8 *putPrereqNameNotInUse(domainname *name, DNSMessage *msg, mDNSu8 *ptr, mDNSu8 *end)
1632 	{
1633 	AuthRecord prereq;
1634 
1635 	mDNSPlatformMemZero(&prereq, sizeof(AuthRecord));
1636 	mDNS_SetupResourceRecord(&prereq, mDNSNULL, mDNSInterface_Any, kDNSQType_ANY, kStandardTTL, 0, mDNSNULL, mDNSNULL);
1637 	AssignDomainName(prereq.resrec.name, name);
1638 	prereq.resrec.rrtype = kDNSQType_ANY;
1639 	prereq.resrec.rrclass = kDNSClass_NONE;
1640 	ptr = putEmptyResourceRecord(msg, ptr, end, &msg->h.mDNS_numPrereqs, &prereq);
1641 	return ptr;
1642 	}
1643 
1644 // for dynamic updates
1645 mDNSexport mDNSu8 *putDeletionRecord(DNSMessage *msg, mDNSu8 *ptr, ResourceRecord *rr)
1646 	{
1647 	mDNSu16 origclass;
1648 	// deletion: specify record w/ TTL 0, class NONE
1649 
1650 	origclass = rr->rrclass;
1651 	rr->rrclass = kDNSClass_NONE;
1652 	ptr = PutResourceRecordTTLJumbo(msg, ptr, &msg->h.mDNS_numUpdates, rr, 0);
1653 	rr->rrclass = origclass;
1654 	return ptr;
1655 	}
1656 
1657 mDNSexport mDNSu8 *putDeleteRRSet(DNSMessage *msg, mDNSu8 *ptr, const domainname *name, mDNSu16 rrtype)
1658 	{
1659 	const mDNSu8 *limit = msg->data + AbsoluteMaxDNSMessageData;
1660 	mDNSu16 class = kDNSQClass_ANY;
1661 
1662 	ptr = putDomainNameAsLabels(msg, ptr, limit, name);
1663 	if (!ptr || ptr + 10 >= limit) return mDNSNULL;	// If we're out-of-space, return mDNSNULL
1664 	ptr[0] = (mDNSu8)(rrtype  >> 8);
1665 	ptr[1] = (mDNSu8)(rrtype  &  0xFF);
1666 	ptr[2] = (mDNSu8)(class >> 8);
1667 	ptr[3] = (mDNSu8)(class &  0xFF);
1668 	ptr[4] = ptr[5] = ptr[6] = ptr[7] = 0; // zero ttl
1669 	ptr[8] = ptr[9] = 0; // zero rdlength/rdata
1670 
1671 	msg->h.mDNS_numUpdates++;
1672 	return ptr + 10;
1673 	}
1674 
1675 // for dynamic updates
1676 mDNSexport mDNSu8 *putDeleteAllRRSets(DNSMessage *msg, mDNSu8 *ptr, const domainname *name)
1677 	{
1678 	const mDNSu8 *limit = msg->data + AbsoluteMaxDNSMessageData;
1679 	mDNSu16 class = kDNSQClass_ANY;
1680 	mDNSu16 rrtype = kDNSQType_ANY;
1681 
1682 	ptr = putDomainNameAsLabels(msg, ptr, limit, name);
1683 	if (!ptr || ptr + 10 >= limit) return mDNSNULL;	// If we're out-of-space, return mDNSNULL
1684 	ptr[0] = (mDNSu8)(rrtype  >> 8);
1685 	ptr[1] = (mDNSu8)(rrtype  &  0xFF);
1686 	ptr[2] = (mDNSu8)(class >> 8);
1687 	ptr[3] = (mDNSu8)(class &  0xFF);
1688 	ptr[4] = ptr[5] = ptr[6] = ptr[7] = 0; // zero ttl
1689 	ptr[8] = ptr[9] = 0; // zero rdlength/rdata
1690 
1691 	msg->h.mDNS_numUpdates++;
1692 	return ptr + 10;
1693 	}
1694 
1695 // for dynamic updates
1696 mDNSexport mDNSu8 *putUpdateLease(DNSMessage *msg, mDNSu8 *end, mDNSu32 lease)
1697 	{
1698 	AuthRecord rr;
1699 	ResourceRecord *opt = &rr.resrec;
1700 	rdataOpt *optRD;
1701 
1702 	mDNSPlatformMemZero(&rr, sizeof(AuthRecord));
1703 	mDNS_SetupResourceRecord(&rr, mDNSNULL, mDNSInterface_Any, kDNSType_OPT, kStandardTTL, 0, mDNSNULL, mDNSNULL);
1704 
1705 	opt->RecordType = kDNSRecordTypeKnownUnique;  // to avoid warnings in other layers
1706 	opt->rrtype = kDNSType_OPT;
1707 	opt->rdlength = LEASE_OPT_RDLEN;
1708 	opt->rdestimate = LEASE_OPT_RDLEN;
1709 
1710 	optRD = &rr.resrec.rdata->u.opt;
1711 	optRD->opt = kDNSOpt_Lease;
1712 	optRD->optlen = sizeof(mDNSs32);
1713 	optRD->OptData.lease = lease;
1714 	end = PutResourceRecordTTLJumbo(msg, end, &msg->h.numAdditionals, opt, 0);
1715 	if (!end) { LogMsg("ERROR: putUpdateLease - PutResourceRecordTTL"); return mDNSNULL; }
1716 
1717 	return end;
1718 	}
1719 
1720 // ***************************************************************************
1721 #if COMPILER_LIKES_PRAGMA_MARK
1722 #pragma mark -
1723 #pragma mark - DNS Message Parsing Functions
1724 #endif
1725 
1726 mDNSexport mDNSu32 DomainNameHashValue(const domainname *const name)
1727 	{
1728 	mDNSu32 sum = 0;
1729 	const mDNSu8 *c;
1730 
1731 	for (c = name->c; c[0] != 0 && c[1] != 0; c += 2)
1732 		{
1733 		sum += ((mDNSIsUpperCase(c[0]) ? c[0] + 'a' - 'A' : c[0]) << 8) |
1734 				(mDNSIsUpperCase(c[1]) ? c[1] + 'a' - 'A' : c[1]);
1735 		sum = (sum<<3) | (sum>>29);
1736 		}
1737 	if (c[0]) sum += ((mDNSIsUpperCase(c[0]) ? c[0] + 'a' - 'A' : c[0]) << 8);
1738 	return(sum);
1739 	}
1740 
1741 mDNSexport void SetNewRData(ResourceRecord *const rr, RData *NewRData, mDNSu16 rdlength)
1742 	{
1743 	domainname *target;
1744 	if (NewRData)
1745 		{
1746 		rr->rdata    = NewRData;
1747 		rr->rdlength = rdlength;
1748 		}
1749 	// Must not try to get target pointer until after updating rr->rdata
1750 	target = GetRRDomainNameTarget(rr);
1751 	rr->rdlength   = GetRDLength(rr, mDNSfalse);
1752 	rr->rdestimate = GetRDLength(rr, mDNStrue);
1753 	rr->rdatahash  = target ? DomainNameHashValue(target) : RDataHashValue(rr->rdlength, &rr->rdata->u);
1754 	}
1755 
1756 mDNSexport const mDNSu8 *skipDomainName(const DNSMessage *const msg, const mDNSu8 *ptr, const mDNSu8 *const end)
1757 	{
1758 	mDNSu16 total = 0;
1759 
1760 	if (ptr < (mDNSu8*)msg || ptr >= end)
1761 		{ debugf("skipDomainName: Illegal ptr not within packet boundaries"); return(mDNSNULL); }
1762 
1763 	while (1)						// Read sequence of labels
1764 		{
1765 		const mDNSu8 len = *ptr++;	// Read length of this label
1766 		if (len == 0) return(ptr);	// If length is zero, that means this name is complete
1767 		switch (len & 0xC0)
1768 			{
1769 			case 0x00:	if (ptr + len >= end)					// Remember: expect at least one more byte for the root label
1770 							{ debugf("skipDomainName: Malformed domain name (overruns packet end)"); return(mDNSNULL); }
1771 						if (total + 1 + len >= MAX_DOMAIN_NAME)	// Remember: expect at least one more byte for the root label
1772 							{ debugf("skipDomainName: Malformed domain name (more than 255 characters)"); return(mDNSNULL); }
1773 						ptr += len;
1774 						total += 1 + len;
1775 						break;
1776 
1777 			case 0x40:	debugf("skipDomainName: Extended EDNS0 label types 0x%X not supported", len); return(mDNSNULL);
1778 			case 0x80:	debugf("skipDomainName: Illegal label length 0x%X", len); return(mDNSNULL);
1779 			case 0xC0:	return(ptr+1);
1780 			}
1781 		}
1782 	}
1783 
1784 // Routine to fetch an FQDN from the DNS message, following compression pointers if necessary.
1785 mDNSexport const mDNSu8 *getDomainName(const DNSMessage *const msg, const mDNSu8 *ptr, const mDNSu8 *const end,
1786 	domainname *const name)
1787 	{
1788 	const mDNSu8 *nextbyte = mDNSNULL;					// Record where we got to before we started following pointers
1789 	mDNSu8       *np = name->c;							// Name pointer
1790 	const mDNSu8 *const limit = np + MAX_DOMAIN_NAME;	// Limit so we don't overrun buffer
1791 
1792 	if (ptr < (mDNSu8*)msg || ptr >= end)
1793 		{ debugf("getDomainName: Illegal ptr not within packet boundaries"); return(mDNSNULL); }
1794 
1795 	*np = 0;						// Tentatively place the root label here (may be overwritten if we have more labels)
1796 
1797 	while (1)						// Read sequence of labels
1798 		{
1799 		const mDNSu8 len = *ptr++;	// Read length of this label
1800 		if (len == 0) break;		// If length is zero, that means this name is complete
1801 		switch (len & 0xC0)
1802 			{
1803 			int i;
1804 			mDNSu16 offset;
1805 
1806 			case 0x00:	if (ptr + len >= end)		// Remember: expect at least one more byte for the root label
1807 							{ debugf("getDomainName: Malformed domain name (overruns packet end)"); return(mDNSNULL); }
1808 						if (np + 1 + len >= limit)	// Remember: expect at least one more byte for the root label
1809 							{ debugf("getDomainName: Malformed domain name (more than 255 characters)"); return(mDNSNULL); }
1810 						*np++ = len;
1811 						for (i=0; i<len; i++) *np++ = *ptr++;
1812 						*np = 0;	// Tentatively place the root label here (may be overwritten if we have more labels)
1813 						break;
1814 
1815 			case 0x40:	debugf("getDomainName: Extended EDNS0 label types 0x%X not supported in name %##s", len, name->c);
1816 						return(mDNSNULL);
1817 
1818 			case 0x80:	debugf("getDomainName: Illegal label length 0x%X in domain name %##s", len, name->c); return(mDNSNULL);
1819 
1820 			case 0xC0:	offset = (mDNSu16)((((mDNSu16)(len & 0x3F)) << 8) | *ptr++);
1821 						if (!nextbyte) nextbyte = ptr;	// Record where we got to before we started following pointers
1822 						ptr = (mDNSu8 *)msg + offset;
1823 						if (ptr < (mDNSu8*)msg || ptr >= end)
1824 							{ debugf("getDomainName: Illegal compression pointer not within packet boundaries"); return(mDNSNULL); }
1825 						if (*ptr & 0xC0)
1826 							{ debugf("getDomainName: Compression pointer must point to real label"); return(mDNSNULL); }
1827 						break;
1828 			}
1829 		}
1830 
1831 	if (nextbyte) return(nextbyte);
1832 	else return(ptr);
1833 	}
1834 
1835 mDNSexport const mDNSu8 *skipResourceRecord(const DNSMessage *msg, const mDNSu8 *ptr, const mDNSu8 *end)
1836 	{
1837 	mDNSu16 pktrdlength;
1838 
1839 	ptr = skipDomainName(msg, ptr, end);
1840 	if (!ptr) { debugf("skipResourceRecord: Malformed RR name"); return(mDNSNULL); }
1841 
1842 	if (ptr + 10 > end) { debugf("skipResourceRecord: Malformed RR -- no type/class/ttl/len!"); return(mDNSNULL); }
1843 	pktrdlength = (mDNSu16)((mDNSu16)ptr[8] <<  8 | ptr[9]);
1844 	ptr += 10;
1845 	if (ptr + pktrdlength > end) { debugf("skipResourceRecord: RDATA exceeds end of packet"); return(mDNSNULL); }
1846 
1847 	return(ptr + pktrdlength);
1848 	}
1849 
1850 mDNSexport const mDNSu8 *GetLargeResourceRecord(mDNS *const m, const DNSMessage * const msg, const mDNSu8 *ptr,
1851     const mDNSu8 *end, const mDNSInterfaceID InterfaceID, mDNSu8 RecordType, LargeCacheRecord *largecr)
1852 	{
1853 	CacheRecord *rr = &largecr->r;
1854 	mDNSu16 pktrdlength;
1855 
1856 	if (largecr == &m->rec && largecr->r.resrec.RecordType)
1857 		LogMsg("GetLargeResourceRecord: m->rec appears to be already in use for %s", CRDisplayString(m, &largecr->r));
1858 
1859 	rr->next              = mDNSNULL;
1860 	rr->resrec.name       = &largecr->namestorage;
1861 
1862 	rr->NextInKAList      = mDNSNULL;
1863 	rr->TimeRcvd          = m ? m->timenow : 0;
1864 	rr->DelayDelivery     = 0;
1865 	rr->NextRequiredQuery = m ? m->timenow : 0;		// Will be updated to the real value when we call SetNextCacheCheckTime()
1866 	rr->LastUsed          = m ? m->timenow : 0;
1867 	rr->CRActiveQuestion  = mDNSNULL;
1868 	rr->UnansweredQueries = 0;
1869 	rr->LastUnansweredTime= 0;
1870 	rr->MPUnansweredQ     = 0;
1871 	rr->MPLastUnansweredQT= 0;
1872 	rr->MPUnansweredKA    = 0;
1873 	rr->MPExpectingKA     = mDNSfalse;
1874 	rr->NextInCFList      = mDNSNULL;
1875 
1876 	rr->resrec.InterfaceID       = InterfaceID;
1877 	ptr = getDomainName(msg, ptr, end, rr->resrec.name);
1878 	if (!ptr) { debugf("GetResourceRecord: Malformed RR name"); return(mDNSNULL); }
1879 
1880 	if (ptr + 10 > end) { debugf("GetResourceRecord: Malformed RR -- no type/class/ttl/len!"); return(mDNSNULL); }
1881 
1882 	rr->resrec.rrtype            = (mDNSu16) ((mDNSu16)ptr[0] <<  8 | ptr[1]);
1883 	rr->resrec.rrclass           = (mDNSu16)(((mDNSu16)ptr[2] <<  8 | ptr[3]) & kDNSClass_Mask);
1884 	rr->resrec.rroriginalttl     = (mDNSu32) ((mDNSu32)ptr[4] << 24 | (mDNSu32)ptr[5] << 16 | (mDNSu32)ptr[6] << 8 | ptr[7]);
1885 	if (rr->resrec.rroriginalttl > 0x70000000UL / mDNSPlatformOneSecond && (mDNSs32)rr->resrec.rroriginalttl != -1)
1886 		rr->resrec.rroriginalttl = 0x70000000UL / mDNSPlatformOneSecond;
1887 	// Note: We don't have to adjust m->NextCacheCheck here -- this is just getting a record into memory for
1888 	// us to look at. If we decide to copy it into the cache, then we'll update m->NextCacheCheck accordingly.
1889 	pktrdlength           = (mDNSu16)((mDNSu16)ptr[8] <<  8 | ptr[9]);
1890 	if (ptr[2] & (kDNSClass_UniqueRRSet >> 8))
1891 		RecordType |= kDNSRecordTypePacketUniqueMask;
1892 	ptr += 10;
1893 	if (ptr + pktrdlength > end) { debugf("GetResourceRecord: RDATA exceeds end of packet"); return(mDNSNULL); }
1894 	end = ptr + pktrdlength;		// Adjust end to indicate the end of the rdata for this resource record
1895 
1896 	rr->resrec.rdata = (RData*)&rr->rdatastorage;
1897 	rr->resrec.rdata->MaxRDLength = MaximumRDSize;
1898 
1899 	if (!RecordType) LogMsg("GetLargeResourceRecord: No RecordType for %##s", rr->resrec.name->c);
1900 
1901 	switch (rr->resrec.rrtype)
1902 		{
1903 		case kDNSType_A:	rr->resrec.rdata->u.ipv4.b[0] = ptr[0];
1904 							rr->resrec.rdata->u.ipv4.b[1] = ptr[1];
1905 							rr->resrec.rdata->u.ipv4.b[2] = ptr[2];
1906 							rr->resrec.rdata->u.ipv4.b[3] = ptr[3];
1907 							break;
1908 
1909 		case kDNSType_CNAME:// Same as PTR
1910 		case kDNSType_NS:
1911 		case kDNSType_PTR:	if (!getDomainName(msg, ptr, end, &rr->resrec.rdata->u.name))
1912 								{ debugf("GetResourceRecord: Malformed CNAME/PTR RDATA name"); return(mDNSNULL); }
1913 							//debugf("%##s PTR %##s rdlen %d", rr->resrec.name.c, rr->resrec.rdata->u.name.c, pktrdlength);
1914 							break;
1915 
1916 		case kDNSType_NULL:	//Same as TXT
1917 		case kDNSType_HINFO://Same as TXT
1918 		case kDNSType_TXT:  if (pktrdlength > rr->resrec.rdata->MaxRDLength)
1919 								{
1920 								debugf("GetResourceRecord: %s rdata size (%d) exceeds storage (%d)",
1921 									DNSTypeName(rr->resrec.rrtype), pktrdlength, rr->resrec.rdata->MaxRDLength);
1922 								return(mDNSNULL);
1923 								}
1924 							rr->resrec.rdlength = pktrdlength;
1925 							mDNSPlatformMemCopy(ptr, rr->resrec.rdata->u.data, pktrdlength);
1926 							break;
1927 
1928 		case kDNSType_AAAA:	mDNSPlatformMemCopy(ptr, &rr->resrec.rdata->u.ipv6, sizeof(rr->resrec.rdata->u.ipv6));
1929 							break;
1930 
1931 		case kDNSType_SRV:	rr->resrec.rdata->u.srv.priority = (mDNSu16)((mDNSu16)ptr[0] <<  8 | ptr[1]);
1932 							rr->resrec.rdata->u.srv.weight   = (mDNSu16)((mDNSu16)ptr[2] <<  8 | ptr[3]);
1933 							rr->resrec.rdata->u.srv.port.b[0] = ptr[4];
1934 							rr->resrec.rdata->u.srv.port.b[1] = ptr[5];
1935 							if (!getDomainName(msg, ptr+6, end, &rr->resrec.rdata->u.srv.target))
1936 								{ debugf("GetResourceRecord: Malformed SRV RDATA name"); return(mDNSNULL); }
1937 							//debugf("%##s SRV %##s rdlen %d", rr->resrec.name.c, rr->resrec.rdata->u.srv.target.c, pktrdlength);
1938 							break;
1939 
1940 		case kDNSType_SOA:  ptr = getDomainName(msg, ptr, end, &rr->resrec.rdata->u.soa.mname);
1941 							if (!ptr) { debugf("GetResourceRecord: Malformed SOA RDATA mname"); return mDNSNULL; }
1942 							ptr = getDomainName(msg, ptr, end, &rr->resrec.rdata->u.soa.rname);
1943 							if (!ptr) { debugf("GetResourceRecord: Malformed SOA RDATA rname"); return mDNSNULL; }
1944 			                if (ptr + 0x14 != end) { debugf("GetResourceRecord: Malformed SOA RDATA"); return mDNSNULL; }
1945                 			rr->resrec.rdata->u.soa.serial  = (mDNSs32) ((mDNSs32)ptr[0x00] << 24 | (mDNSs32)ptr[0x01] << 16 | (mDNSs32)ptr[0x02] << 8 | ptr[0x03]);
1946 			                rr->resrec.rdata->u.soa.refresh = (mDNSu32) ((mDNSu32)ptr[0x04] << 24 | (mDNSu32)ptr[0x05] << 16 | (mDNSu32)ptr[0x06] << 8 | ptr[0x07]);
1947 			                rr->resrec.rdata->u.soa.retry   = (mDNSu32) ((mDNSu32)ptr[0x08] << 24 | (mDNSu32)ptr[0x09] << 16 | (mDNSu32)ptr[0x0A] << 8 | ptr[0x0B]);
1948 			                rr->resrec.rdata->u.soa.expire  = (mDNSu32) ((mDNSu32)ptr[0x0C] << 24 | (mDNSu32)ptr[0x0D] << 16 | (mDNSu32)ptr[0x0E] << 8 | ptr[0x0F]);
1949 			                rr->resrec.rdata->u.soa.min     = (mDNSu32) ((mDNSu32)ptr[0x10] << 24 | (mDNSu32)ptr[0x11] << 16 | (mDNSu32)ptr[0x12] << 8 | ptr[0x13]);
1950 			                break;
1951 
1952 		case kDNSType_OPT:  getOptRdata(ptr, end, largecr, pktrdlength); break;
1953 
1954 		default:			if (pktrdlength > rr->resrec.rdata->MaxRDLength)
1955 								{
1956 								debugf("GetResourceRecord: rdata %d (%s) size (%d) exceeds storage (%d)",
1957 									rr->resrec.rrtype, DNSTypeName(rr->resrec.rrtype), pktrdlength, rr->resrec.rdata->MaxRDLength);
1958 								return(mDNSNULL);
1959 								}
1960 							debugf("GetResourceRecord: Warning! Reading resource type %d (%s) as opaque data",
1961 								rr->resrec.rrtype, DNSTypeName(rr->resrec.rrtype));
1962 							// Note: Just because we don't understand the record type, that doesn't
1963 							// mean we fail. The DNS protocol specifies rdlength, so we can
1964 							// safely skip over unknown records and ignore them.
1965 							// We also grab a binary copy of the rdata anyway, since the caller
1966 							// might know how to interpret it even if we don't.
1967 							rr->resrec.rdlength = pktrdlength;
1968 							mDNSPlatformMemCopy(ptr, rr->resrec.rdata->u.data, pktrdlength);
1969 							break;
1970 		}
1971 
1972 	rr->resrec.namehash = DomainNameHashValue(rr->resrec.name);
1973 	SetNewRData(&rr->resrec, mDNSNULL, 0);
1974 
1975 	// Success! Now fill in RecordType to show this record contains valid data
1976 	rr->resrec.RecordType = RecordType;
1977 	return(ptr + pktrdlength);
1978 	}
1979 
1980 mDNSexport const mDNSu8 *skipQuestion(const DNSMessage *msg, const mDNSu8 *ptr, const mDNSu8 *end)
1981 	{
1982 	ptr = skipDomainName(msg, ptr, end);
1983 	if (!ptr) { debugf("skipQuestion: Malformed domain name in DNS question section"); return(mDNSNULL); }
1984 	if (ptr+4 > end) { debugf("skipQuestion: Malformed DNS question section -- no query type and class!"); return(mDNSNULL); }
1985 	return(ptr+4);
1986 	}
1987 
1988 mDNSexport const mDNSu8 *getQuestion(const DNSMessage *msg, const mDNSu8 *ptr, const mDNSu8 *end, const mDNSInterfaceID InterfaceID,
1989 	DNSQuestion *question)
1990 	{
1991 	question->InterfaceID = InterfaceID;
1992 	ptr = getDomainName(msg, ptr, end, &question->qname);
1993 	if (!ptr) { debugf("Malformed domain name in DNS question section"); return(mDNSNULL); }
1994 	if (ptr+4 > end) { debugf("Malformed DNS question section -- no query type and class!"); return(mDNSNULL); }
1995 
1996 	question->qnamehash = DomainNameHashValue(&question->qname);
1997 	question->qtype  = (mDNSu16)((mDNSu16)ptr[0] << 8 | ptr[1]);			// Get type
1998 	question->qclass = (mDNSu16)((mDNSu16)ptr[2] << 8 | ptr[3]);			// and class
1999 	return(ptr+4);
2000 	}
2001 
2002 mDNSexport const mDNSu8 *LocateAnswers(const DNSMessage *const msg, const mDNSu8 *const end)
2003 	{
2004 	int i;
2005 	const mDNSu8 *ptr = msg->data;
2006 	for (i = 0; i < msg->h.numQuestions && ptr; i++) ptr = skipQuestion(msg, ptr, end);
2007 	return(ptr);
2008 	}
2009 
2010 mDNSexport const mDNSu8 *LocateAuthorities(const DNSMessage *const msg, const mDNSu8 *const end)
2011 	{
2012 	int i;
2013 	const mDNSu8 *ptr = LocateAnswers(msg, end);
2014 	for (i = 0; i < msg->h.numAnswers && ptr; i++) ptr = skipResourceRecord(msg, ptr, end);
2015 	return(ptr);
2016 	}
2017 
2018 mDNSexport const mDNSu8 *LocateAdditionals(const DNSMessage *const msg, const mDNSu8 *const end)
2019 	{
2020 	int i;
2021 	const mDNSu8 *ptr = LocateAuthorities(msg, end);
2022 	for (i = 0; i < msg->h.numAuthorities; i++) ptr = skipResourceRecord(msg, ptr, end);
2023 	return (ptr);
2024 	}
2025 
2026 // ***************************************************************************
2027 #if COMPILER_LIKES_PRAGMA_MARK
2028 #pragma mark -
2029 #pragma mark -
2030 #pragma mark - Packet Sending Functions
2031 #endif
2032 
2033 mDNSexport mStatus mDNSSendDNSMessage(const mDNS *const m, DNSMessage *const msg, mDNSu8 *end,
2034     mDNSInterfaceID InterfaceID, const mDNSAddr *dst, mDNSIPPort dstport, int sd, uDNS_AuthInfo *authInfo)
2035 	{
2036 	mStatus status;
2037 	int nsent;
2038 	mDNSs32 msglen;
2039 	mDNSu8 lenbuf[2];
2040 	mDNSu16 numQuestions   = msg->h.numQuestions;
2041 	mDNSu16 numAnswers     = msg->h.numAnswers;
2042 	mDNSu16 numAuthorities = msg->h.numAuthorities;
2043 	mDNSu16 numAdditionals = msg->h.numAdditionals;
2044 	mDNSu8 *ptr = (mDNSu8 *)&msg->h.numQuestions;
2045 
2046 	// Put all the integer values in IETF byte-order (MSB first, LSB second)
2047 	*ptr++ = (mDNSu8)(numQuestions   >> 8);
2048 	*ptr++ = (mDNSu8)(numQuestions   &  0xFF);
2049 	*ptr++ = (mDNSu8)(numAnswers     >> 8);
2050 	*ptr++ = (mDNSu8)(numAnswers     &  0xFF);
2051 	*ptr++ = (mDNSu8)(numAuthorities >> 8);
2052 	*ptr++ = (mDNSu8)(numAuthorities &  0xFF);
2053 	*ptr++ = (mDNSu8)(numAdditionals >> 8);
2054 	*ptr++ = (mDNSu8)(numAdditionals &  0xFF);
2055 
2056 	if (authInfo)
2057 		{
2058 		end = DNSDigest_SignMessage(msg, &end, &numAdditionals, authInfo);
2059 		if (!end) return mStatus_UnknownErr;
2060 		}
2061 
2062 	// Send the packet on the wire
2063 
2064 	if (sd >= 0)
2065 		{
2066 		msglen = (mDNSu16)(end - (mDNSu8 *)msg);
2067 		lenbuf[0] = (mDNSu8)(msglen >> 8);  // host->network byte conversion
2068 		lenbuf[1] = (mDNSu8)(msglen &  0xFF);
2069 		nsent = mDNSPlatformWriteTCP(sd, (char*)lenbuf, 2);
2070 		//!!!KRS make sure kernel is sending these as 1 packet!
2071 		if (nsent != 2) goto tcp_error;
2072 		nsent = mDNSPlatformWriteTCP(sd, (char *)msg, msglen);
2073 		if (nsent != msglen) goto tcp_error;
2074 		status = mStatus_NoError;
2075 		}
2076 	else
2077 		{
2078 		status = mDNSPlatformSendUDP(m, msg, end, InterfaceID, dst, dstport);
2079 		}
2080 
2081 	// Put all the integer values back the way they were before we return
2082 	msg->h.numQuestions   = numQuestions;
2083 	msg->h.numAnswers     = numAnswers;
2084 	msg->h.numAuthorities = numAuthorities;
2085 	msg->h.numAdditionals = (mDNSu16)(authInfo ? numAdditionals - 1 : numAdditionals);
2086 
2087 	return(status);
2088 
2089 	tcp_error:
2090 	LogMsg("mDNSSendDNSMessage: error sending message over tcp");
2091 	return mStatus_UnknownErr;
2092 	}
2093 
2094 // ***************************************************************************
2095 #if COMPILER_LIKES_PRAGMA_MARK
2096 #pragma mark -
2097 #pragma mark - RR List Management & Task Management
2098 #endif
2099 
2100 mDNSexport void mDNS_Lock(mDNS *const m)
2101 	{
2102 	// MUST grab the platform lock FIRST!
2103 	mDNSPlatformLock(m);
2104 
2105 	// Normally, mDNS_reentrancy is zero and so is mDNS_busy
2106 	// However, when we call a client callback mDNS_busy is one, and we increment mDNS_reentrancy too
2107 	// If that client callback does mDNS API calls, mDNS_reentrancy and mDNS_busy will both be one
2108 	// If mDNS_busy != mDNS_reentrancy that's a bad sign
2109 	if (m->mDNS_busy != m->mDNS_reentrancy)
2110 		LogMsg("mDNS_Lock: Locking failure! mDNS_busy (%ld) != mDNS_reentrancy (%ld)", m->mDNS_busy, m->mDNS_reentrancy);
2111 
2112 	// If this is an initial entry into the mDNSCore code, set m->timenow
2113 	// else, if this is a re-entrant entry into the mDNSCore code, m->timenow should already be set
2114 	if (m->mDNS_busy == 0)
2115 		{
2116 		if (m->timenow)
2117 			LogMsg("mDNS_Lock: m->timenow already set (%ld/%ld)", m->timenow, mDNS_TimeNow_NoLock(m));
2118 		m->timenow = mDNS_TimeNow_NoLock(m);
2119 		if (m->timenow == 0) m->timenow = 1;
2120 		}
2121 	else if (m->timenow == 0)
2122 		{
2123 		LogMsg("mDNS_Lock: m->mDNS_busy is %ld but m->timenow not set", m->mDNS_busy);
2124 		m->timenow = mDNS_TimeNow_NoLock(m);
2125 		if (m->timenow == 0) m->timenow = 1;
2126 		}
2127 
2128 	if (m->timenow_last - m->timenow > 0)
2129 		{
2130 		m->timenow_adjust += m->timenow_last - m->timenow;
2131 		LogMsg("mDNSPlatformRawTime went backwards by %ld ticks; setting correction factor to %ld", m->timenow_last - m->timenow, m->timenow_adjust);
2132 		m->timenow = m->timenow_last;
2133 		}
2134 	m->timenow_last = m->timenow;
2135 
2136 	// Increment mDNS_busy so we'll recognise re-entrant calls
2137 	m->mDNS_busy++;
2138 	}
2139 
2140 mDNSlocal mDNSs32 GetNextScheduledEvent(const mDNS *const m)
2141 	{
2142 	mDNSs32 e = m->timenow + 0x78000000;
2143 	if (m->mDNSPlatformStatus != mStatus_NoError || m->SleepState) return(e);
2144 	if (m->NewQuestions)
2145 		{
2146 		if (m->NewQuestions->DelayAnswering) e = m->NewQuestions->DelayAnswering;
2147 		else return(m->timenow);
2148 		}
2149 	if (m->NewLocalOnlyQuestions)                                   return(m->timenow);
2150 	if (m->NewLocalRecords && LocalRecordReady(m->NewLocalRecords)) return(m->timenow);
2151 	if (m->SuppressSending)                                         return(m->SuppressSending);
2152 #ifndef UNICAST_DISABLED
2153 	if (e - m->uDNS_info.nextevent   > 0) e = m->uDNS_info.nextevent;
2154 #endif
2155 	if (e - m->NextCacheCheck        > 0) e = m->NextCacheCheck;
2156 	if (e - m->NextScheduledQuery    > 0) e = m->NextScheduledQuery;
2157 	if (e - m->NextScheduledProbe    > 0) e = m->NextScheduledProbe;
2158 	if (e - m->NextScheduledResponse > 0) e = m->NextScheduledResponse;
2159 	return(e);
2160 	}
2161 
2162 mDNSexport void mDNS_Unlock(mDNS *const m)
2163 	{
2164 	// Decrement mDNS_busy
2165 	m->mDNS_busy--;
2166 
2167 	// Check for locking failures
2168 	if (m->mDNS_busy != m->mDNS_reentrancy)
2169 		LogMsg("mDNS_Unlock: Locking failure! mDNS_busy (%ld) != mDNS_reentrancy (%ld)", m->mDNS_busy, m->mDNS_reentrancy);
2170 
2171 	// If this is a final exit from the mDNSCore code, set m->NextScheduledEvent and clear m->timenow
2172 	if (m->mDNS_busy == 0)
2173 		{
2174 		m->NextScheduledEvent = GetNextScheduledEvent(m);
2175 		if (m->timenow == 0) LogMsg("mDNS_Unlock: ERROR! m->timenow aready zero");
2176 		m->timenow = 0;
2177 		}
2178 
2179 	// MUST release the platform lock LAST!
2180 	mDNSPlatformUnlock(m);
2181 	}
2182