diff options
author | Jonathan McCrohan <jmccrohan@gmail.com> | 2012-04-14 12:56:48 +0100 |
---|---|---|
committer | Jonathan McCrohan <jmccrohan@gmail.com> | 2012-04-14 12:56:48 +0100 |
commit | 0b624384cd52be20e61284551d832b499d7b7707 (patch) | |
tree | 6f95a4bbef47abc9720b96c0722e8f632aef228a /utils | |
download | libphidget21-0b624384cd52be20e61284551d832b499d7b7707.tar.gz |
Imported Upstream version 2.1.8.20120216upstream/2.1.8.20120216
Diffstat (limited to '')
-rw-r--r-- | utils/cvtutf.c | 339 | ||||
-rw-r--r-- | utils/cvtutf.h | 110 | ||||
-rw-r--r-- | utils/md5.c | 382 | ||||
-rw-r--r-- | utils/md5.h | 91 | ||||
-rw-r--r-- | utils/plist.c | 151 | ||||
-rw-r--r-- | utils/plist.h | 13 | ||||
-rw-r--r-- | utils/ptree.c | 460 | ||||
-rw-r--r-- | utils/ptree.h | 33 | ||||
-rw-r--r-- | utils/utils.c | 1223 | ||||
-rw-r--r-- | utils/utils.h | 49 |
10 files changed, 2851 insertions, 0 deletions
diff --git a/utils/cvtutf.c b/utils/cvtutf.c new file mode 100644 index 0000000..8110c74 --- /dev/null +++ b/utils/cvtutf.c @@ -0,0 +1,339 @@ +/* ================================================================ */
+/*
+File: ConvertUTF.C
+Author: Mark E. Davis
+Copyright (C) 1994 Taligent, Inc. All rights reserved.
+
+This code is copyrighted. Under the copyright laws, this code may not
+be copied, in whole or part, without prior written consent of Taligent.
+
+Taligent grants the right to use or reprint this code as long as this
+ENTIRE copyright notice is reproduced in the code or reproduction.
+The code is provided AS-IS, AND TALIGENT DISCLAIMS ALL WARRANTIES,
+EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN
+NO EVENT WILL TALIGENT BE LIABLE FOR ANY DAMAGES WHATSOEVER (INCLUDING,
+WITHOUT LIMITATION, DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS
+INTERRUPTION, LOSS OF BUSINESS INFORMATION, OR OTHER PECUNIARY
+LOSS) ARISING OUT OF THE USE OR INABILITY TO USE THIS CODE, EVEN
+IF TALIGENT HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+BECAUSE SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF
+LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES, THE ABOVE
+LIMITATION MAY NOT APPLY TO YOU.
+
+RESTRICTED RIGHTS LEGEND: Use, duplication, or disclosure by the
+government is subject to restrictions as set forth in subparagraph
+(c)(l)(ii) of the Rights in Technical Data and Computer Software
+clause at DFARS 252.227-7013 and FAR 52.227-19.
+
+This code may be protected by one or more U.S. and International
+Patents.
+
+TRADEMARKS: Taligent and the Taligent Design Mark are registered
+trademarks of Taligent, Inc.
+*/
+/* ================================================================ */
+
+#include "cvtutf.h"
+
+/* ================================================================ */
+
+static const int halfShift = 10;
+static const UCS4 halfBase = 0x0010000UL;
+static const UCS4 halfMask = 0x3FFUL;
+static const UCS4 kSurrogateHighStart = 0xD800UL;
+static const UCS4 kSurrogateHighEnd = 0xDBFFUL;
+static const UCS4 kSurrogateLowStart = 0xDC00UL;
+static const UCS4 kSurrogateLowEnd = 0xDFFFUL;
+
+/* ================================================================ */
+
+ConversionResult
+ConvertUCS4toUTF16(UCS4** sourceStart, const UCS4* sourceEnd,
+ UTF16** targetStart, const UTF16* targetEnd)
+{
+ ConversionResult result = ok;
+ register UCS4* source = *sourceStart;
+ register UTF16* target = *targetStart;
+ while (source < sourceEnd) {
+ register UCS4 ch;
+ if (target >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ ch = *source++;
+ if (ch <= kMaximumUCS2) {
+ *target++ = ch;
+ } else if (ch > kMaximumUTF16) {
+ *target++ = kReplacementCharacter;
+ } else {
+ if (target + 1 >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ ch -= halfBase;
+ *target++ = (ch >> halfShift) + kSurrogateHighStart;
+ *target++ = (ch & halfMask) + kSurrogateLowStart;
+ };
+ };
+ *sourceStart = source;
+ *targetStart = target;
+ return result;
+};
+
+/* ================================================================ */
+
+ConversionResult ConvertUTF16toUCS4(UTF16** sourceStart, UTF16* sourceEnd,
+ UCS4** targetStart, const UCS4* targetEnd)
+{
+ ConversionResult result = ok;
+ register UTF16* source = *sourceStart;
+ register UCS4* target = *targetStart;
+ while (source < sourceEnd) {
+ register UCS4 ch;
+ ch = *source++;
+ if (ch >= kSurrogateHighStart &&
+ ch <= kSurrogateHighEnd &&
+ source < sourceEnd) {
+ register UCS4 ch2 = *source;
+ if (ch2 >= kSurrogateLowStart && ch2 <= kSurrogateLowEnd) {
+ ch = ((ch - kSurrogateHighStart) << halfShift)
+ + (ch2 - kSurrogateLowStart) + halfBase;
+ ++source;
+ };
+ };
+ if (target >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ *target++ = ch;
+ };
+ *sourceStart = source;
+ *targetStart = target;
+ return result;
+};
+
+/* ================================================================ */
+
+static UCS4 offsetsFromUTF8[6] = {
+ 0x00000000UL, 0x00003080UL, 0x000E2080UL,
+ 0x03C82080UL, 0xFA082080UL, 0x82082080UL
+};
+static char bytesFromUTF8[256] = {
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
+ 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5
+};
+
+static UTF8 firstByteMark[7] = {0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC};
+
+/* ================================================================ */
+/* This code is similar in effect to making successive calls on the
+mbtowc and wctomb routines in FSS-UTF. However, it is considerably
+different in code:
+* it is adapted to be consistent with UTF16,
+* the interface converts a whole buffer to avoid function-call overhead
+* constants have been gathered.
+* loops & conditionals have been removed as much as possible for
+efficiency, in favor of drop-through switch statements.
+*/
+
+/* ================================================================ */
+int NSConvertUTF16toUTF8(unichar **sourceStart,
+ const unichar *sourceEnd,
+ unsigned char **targetStart,
+ const unsigned char *targetEnd)
+{
+ ConversionResult result = ok;
+ register UTF16* source = *sourceStart;
+ register UTF8* target = *targetStart;
+ while (source < sourceEnd) {
+ register UCS4 ch;
+ register unsigned short bytesToWrite = 0;
+ register const UCS4 byteMask = 0xBF;
+ register const UCS4 byteMark = 0x80;
+ ch = *source++;
+ if (ch >= kSurrogateHighStart && ch <= kSurrogateHighEnd
+ && source < sourceEnd) {
+ register UCS4 ch2 = *source;
+ if (ch2 >= kSurrogateLowStart && ch2 <= kSurrogateLowEnd) {
+ ch = ((ch - kSurrogateHighStart) << halfShift)
+ + (ch2 - kSurrogateLowStart) + halfBase;
+ ++source;
+ };
+ };
+ if (ch < 0x80) { bytesToWrite = 1;
+ } else if (ch < 0x800) { bytesToWrite = 2;
+ } else if (ch < 0x10000) { bytesToWrite = 3;
+ } else if (ch < 0x200000) { bytesToWrite = 4;
+ } else if (ch < 0x4000000) { bytesToWrite = 5;
+ } else if (ch <= kMaximumUCS4){ bytesToWrite = 6;
+ } else { bytesToWrite = 2;
+ ch = kReplacementCharacter;
+ }; /* I wish there were a smart way to avoid this conditional */
+
+ target += bytesToWrite;
+ if (target > targetEnd) {
+ target -= bytesToWrite; result = targetExhausted; break;
+ };
+ switch (bytesToWrite) { /* note: code falls through cases! */
+ case 6: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 5: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 4: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 3: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 2: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 1: *--target = ch | firstByteMark[bytesToWrite];
+ };
+ target += bytesToWrite;
+ };
+ *sourceStart = source;
+ *targetStart = target;
+
+ return result;
+};
+
+/* ================================================================ */
+
+int NSConvertUTF8toUTF16(unsigned char **sourceStart, unsigned char *sourceEnd,
+ unichar **targetStart, const unichar *targetEnd)
+{
+ ConversionResult result = ok;
+ register UTF8 *source = *sourceStart;
+ register UTF16 *target = *targetStart;
+
+ while (source < sourceEnd) {
+ register UCS4 ch = 0;
+ register unsigned short extraBytesToWrite = bytesFromUTF8[*source];
+
+ if (source + extraBytesToWrite > sourceEnd) {
+ result = sourceExhausted; break;
+ };
+ switch(extraBytesToWrite) { /* note: code falls through cases! */
+ case 5: ch += *source++; ch <<= 6;
+ case 4: ch += *source++; ch <<= 6;
+ case 3: ch += *source++; ch <<= 6;
+ case 2: ch += *source++; ch <<= 6;
+ case 1: ch += *source++; ch <<= 6;
+ case 0: ch += *source++;
+ };
+ ch -= offsetsFromUTF8[extraBytesToWrite];
+
+ if (target >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ if (ch <= kMaximumUCS2) {
+ *target++ = ch;
+ } else if (ch > kMaximumUTF16) {
+ *target++ = kReplacementCharacter;
+ } else {
+ if (target + 1 >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ ch -= halfBase;
+ *target++ = (ch >> halfShift) + kSurrogateHighStart;
+ *target++ = (ch & halfMask) + kSurrogateLowStart;
+ };
+ };
+ *sourceStart = source;
+ *targetStart = target;
+
+ return result;
+};
+
+/* ================================================================ */
+ConversionResult ConvertUCS4toUTF8 ( UCS4** sourceStart, const UCS4* sourceEnd,
+ UTF8** targetStart, const UTF8* targetEnd)
+{
+ ConversionResult result = ok;
+ register UCS4* source = *sourceStart;
+ register UTF8* target = *targetStart;
+ while (source < sourceEnd) {
+ register UCS4 ch;
+ register unsigned short bytesToWrite = 0;
+ register const UCS4 byteMask = 0xBF;
+ register const UCS4 byteMark = 0x80;
+ ch = *source++;
+ if (ch >= kSurrogateHighStart && ch <= kSurrogateHighEnd
+ && source < sourceEnd) {
+ register UCS4 ch2 = *source;
+ if (ch2 >= kSurrogateLowStart && ch2 <= kSurrogateLowEnd) {
+ ch = ((ch - kSurrogateHighStart) << halfShift)
+ + (ch2 - kSurrogateLowStart) + halfBase;
+ ++source;
+ };
+ };
+ if (ch < 0x80) { bytesToWrite = 1;
+ } else if (ch < 0x800) { bytesToWrite = 2;
+ } else if (ch < 0x10000) { bytesToWrite = 3;
+ } else if (ch < 0x200000) { bytesToWrite = 4;
+ } else if (ch < 0x4000000) { bytesToWrite = 5;
+ } else if (ch <= kMaximumUCS4){ bytesToWrite = 6;
+ } else { bytesToWrite = 2;
+ ch = kReplacementCharacter;
+ }; /* I wish there were a smart way to avoid this conditional */
+
+ target += bytesToWrite;
+ if (target > targetEnd) {
+ target -= bytesToWrite; result = targetExhausted; break;
+ };
+ switch (bytesToWrite) { /* note: code falls through cases! */
+ case 6: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 5: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 4: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 3: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 2: *--target = (ch | byteMark) & byteMask; ch >>= 6;
+ case 1: *--target = ch | firstByteMark[bytesToWrite];
+ };
+ target += bytesToWrite;
+ };
+ *sourceStart = source;
+ *targetStart = target;
+ return result;
+};
+
+/* ================================================================ */
+
+ConversionResult ConvertUTF8toUCS4 (UTF8** sourceStart, UTF8* sourceEnd,
+ UCS4** targetStart, const UCS4* targetEnd)
+{
+ ConversionResult result = ok;
+ register UTF8* source = *sourceStart;
+ register UCS4* target = *targetStart;
+ while (source < sourceEnd) {
+ register UCS4 ch = 0;
+ register unsigned short extraBytesToWrite = bytesFromUTF8[*source];
+ if (source + extraBytesToWrite > sourceEnd) {
+ result = sourceExhausted; break;
+ };
+ switch(extraBytesToWrite) { /* note: code falls through cases! */
+ case 5: ch += *source++; ch <<= 6;
+ case 4: ch += *source++; ch <<= 6;
+ case 3: ch += *source++; ch <<= 6;
+ case 2: ch += *source++; ch <<= 6;
+ case 1: ch += *source++; ch <<= 6;
+ case 0: ch += *source++;
+ };
+ ch -= offsetsFromUTF8[extraBytesToWrite];
+
+ if (target >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ if (ch <= kMaximumUCS2) {
+ *target++ = ch;
+ } else if (ch > kMaximumUCS4) {
+ *target++ = kReplacementCharacter;
+ } else {
+ if (target + 1 >= targetEnd) {
+ result = targetExhausted; break;
+ };
+ ch -= halfBase;
+ *target++ = (ch >> halfShift) + kSurrogateHighStart;
+ *target++ = (ch & halfMask) + kSurrogateLowStart;
+ };
+ };
+ *sourceStart = source;
+ *targetStart = target;
+ return result;
+};
diff --git a/utils/cvtutf.h b/utils/cvtutf.h new file mode 100644 index 0000000..1d9f8ec --- /dev/null +++ b/utils/cvtutf.h @@ -0,0 +1,110 @@ +/* ================================================================ */
+/*
+File: ConvertUTF.h
+Author: Mark E. Davis
+Copyright (C) 1994 Taligent, Inc. All rights reserved.
+
+This code is copyrighted. Under the copyright laws, this code may not
+be copied, in whole or part, without prior written consent of Taligent.
+
+Taligent grants the right to use or reprint this code as long as this
+ENTIRE copyright notice is reproduced in the code or reproduction.
+The code is provided AS-IS, AND TALIGENT DISCLAIMS ALL WARRANTIES,
+EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN
+NO EVENT WILL TALIGENT BE LIABLE FOR ANY DAMAGES WHATSOEVER (INCLUDING,
+WITHOUT LIMITATION, DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS
+INTERRUPTION, LOSS OF BUSINESS INFORMATION, OR OTHER PECUNIARY
+LOSS) ARISING OUT OF THE USE OR INABILITY TO USE THIS CODE, EVEN
+IF TALIGENT HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+BECAUSE SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF
+LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES, THE ABOVE
+LIMITATION MAY NOT APPLY TO YOU.
+
+RESTRICTED RIGHTS LEGEND: Use, duplication, or disclosure by the
+government is subject to restrictions as set forth in subparagraph
+(c)(l)(ii) of the Rights in Technical Data and Computer Software
+clause at DFARS 252.227-7013 and FAR 52.227-19.
+
+This code may be protected by one or more U.S. and International
+Patents.
+
+TRADEMARKS: Taligent and the Taligent Design Mark are registered
+trademarks of Taligent, Inc.
+*/
+/* ================================================================ */
+
+#ifndef __cvtutf_H__
+#define __cvtutf_H__
+
+#include <stdio.h>
+#include <stdlib.h>
+// #include <types.h>
+#include <string.h>
+
+/* ================================================================ */
+/* The following 4 definitions are compiler-specific.
+ I would use wchar_t for UCS2/UTF16, except that the C standard
+ does not guarantee that it has at least 16 bits, so wchar_t is
+ no less portable than unsigned short!
+*/
+
+typedef unsigned long UCS4;
+typedef unsigned short UCS2;
+typedef unsigned short UTF16;
+typedef unsigned char UTF8;
+#define unichar UTF16
+
+//typedef enum {false, true} Boolean;
+
+static const UCS4 kReplacementCharacter = 0x0000FFFDUL;
+static const UCS4 kMaximumUCS2 = 0x0000FFFFUL;
+static const UCS4 kMaximumUTF16 = 0x0010FFFFUL;
+static const UCS4 kMaximumUCS4 = 0x7FFFFFFFUL;
+
+/* ================================================================ */
+/* Each of these routines converts the text between *sourceStart and
+sourceEnd, putting the result into the buffer between *targetStart and
+targetEnd. Note: the end pointers are *after* the last item: e.g.
+*(sourceEnd - 1) is the last item.
+
+ The return result indicates whether the conversion was successful,
+and if not, whether the problem was in the source or target buffers.
+
+ After the conversion, *sourceStart and *targetStart are both
+updated to point to the end of last text successfully converted in
+the respective buffers.
+*/
+
+typedef enum {
+ ok, /* conversion successful */
+ sourceExhausted, /* partial character in source, but hit end */
+ targetExhausted /* insuff. room in target for conversion */
+} ConversionResult;
+
+ConversionResult ConvertUCS4toUTF16 (
+ UCS4** sourceStart, const UCS4* sourceEnd,
+ UTF16** targetStart, const UTF16* targetEnd);
+
+ConversionResult ConvertUTF16toUCS4 (
+ UTF16** sourceStart, UTF16* sourceEnd,
+ UCS4** targetStart, const UCS4* targetEnd);
+
+int NSConvertUTF16toUTF8(unichar **sourceStart,
+ const unichar *sourceEnd,
+ unsigned char **targetStart,
+ const unsigned char *targetEnd);
+int NSConvertUTF8toUTF16(unsigned char **sourceStart, unsigned char *sourceEnd,
+ unichar **targetStart, const unichar *targetEnd);
+
+ConversionResult ConvertUCS4toUTF8 (
+ UCS4** sourceStart, const UCS4* sourceEnd,
+ UTF8** targetStart, const UTF8* targetEnd);
+
+ConversionResult ConvertUTF8toUCS4 (
+ UTF8** sourceStart, UTF8* sourceEnd,
+ UCS4** targetStart, const UCS4* targetEnd);
+
+/* ================================================================ */
+
+#endif /* __cvtutf_H__ */
diff --git a/utils/md5.c b/utils/md5.c new file mode 100644 index 0000000..b0f715e --- /dev/null +++ b/utils/md5.c @@ -0,0 +1,382 @@ +/* + Copyright (C) 1999, 2000, 2002 Aladdin Enterprises. All rights reserved. + + This software is provided 'as-is', without any express or implied + warranty. In no event will the authors be held liable for any damages + arising from the use of this software. + + Permission is granted to anyone to use this software for any purpose, + including commercial applications, and to alter it and redistribute it + freely, subject to the following restrictions: + + 1. The origin of this software must not be misrepresented; you must not + claim that you wrote the original software. If you use this software + in a product, an acknowledgment in the product documentation would be + appreciated but is not required. + 2. Altered source versions must be plainly marked as such, and must not be + misrepresented as being the original software. + 3. This notice may not be removed or altered from any source distribution. + + L. Peter Deutsch + ghost@aladdin.com + + */ +/* $Id: md5.c 15582 2010-06-15 17:50:08Z patrick $ */ +/* + Independent implementation of MD5 (RFC 1321). + + This code implements the MD5 Algorithm defined in RFC 1321, whose + text is available at + http://www.ietf.org/rfc/rfc1321.txt + The code is derived from the text of the RFC, including the test suite + (section A.5) but excluding the rest of Appendix A. It does not include + any code or documentation that is identified in the RFC as being + copyrighted. + + The original and principal author of md5.c is L. Peter Deutsch + <ghost@aladdin.com>. Other authors are noted in the change history + that follows (in reverse chronological order): + + 2002-04-13 lpd Clarified derivation from RFC 1321; now handles byte order + either statically or dynamically; added missing #include <string.h> + in library. + 2002-03-11 lpd Corrected argument list for main(), and added int return + type, in test program and T value program. + 2002-02-21 lpd Added missing #include <stdio.h> in test program. + 2000-07-03 lpd Patched to eliminate warnings about "constant is + unsigned in ANSI C, signed in traditional"; made test program + self-checking. + 1999-11-04 lpd Edited comments slightly for automatic TOC extraction. + 1999-10-18 lpd Fixed typo in header comment (ansi2knr rather than md5). + 1999-05-03 lpd Original version. + */ + +#include "../stdafx.h" +#include "md5.h" +#include <string.h> + +#undef BYTE_ORDER /* 1 = big-endian, -1 = little-endian, 0 = unknown */ +#ifdef ARCH_IS_BIG_ENDIAN +# define BYTE_ORDER (ARCH_IS_BIG_ENDIAN ? 1 : -1) +#else +# define BYTE_ORDER 0 +#endif + +#define T_MASK ((md5_word_t)~0) +#define T1 /* 0xd76aa478 */ (T_MASK ^ 0x28955b87) +#define T2 /* 0xe8c7b756 */ (T_MASK ^ 0x173848a9) +#define T3 0x242070db +#define T4 /* 0xc1bdceee */ (T_MASK ^ 0x3e423111) +#define T5 /* 0xf57c0faf */ (T_MASK ^ 0x0a83f050) +#define T6 0x4787c62a +#define T7 /* 0xa8304613 */ (T_MASK ^ 0x57cfb9ec) +#define T8 /* 0xfd469501 */ (T_MASK ^ 0x02b96afe) +#define T9 0x698098d8 +#define T10 /* 0x8b44f7af */ (T_MASK ^ 0x74bb0850) +#define T11 /* 0xffff5bb1 */ (T_MASK ^ 0x0000a44e) +#define T12 /* 0x895cd7be */ (T_MASK ^ 0x76a32841) +#define T13 0x6b901122 +#define T14 /* 0xfd987193 */ (T_MASK ^ 0x02678e6c) +#define T15 /* 0xa679438e */ (T_MASK ^ 0x5986bc71) +#define T16 0x49b40821 +#define T17 /* 0xf61e2562 */ (T_MASK ^ 0x09e1da9d) +#define T18 /* 0xc040b340 */ (T_MASK ^ 0x3fbf4cbf) +#define T19 0x265e5a51 +#define T20 /* 0xe9b6c7aa */ (T_MASK ^ 0x16493855) +#define T21 /* 0xd62f105d */ (T_MASK ^ 0x29d0efa2) +#define T22 0x02441453 +#define T23 /* 0xd8a1e681 */ (T_MASK ^ 0x275e197e) +#define T24 /* 0xe7d3fbc8 */ (T_MASK ^ 0x182c0437) +#define T25 0x21e1cde6 +#define T26 /* 0xc33707d6 */ (T_MASK ^ 0x3cc8f829) +#define T27 /* 0xf4d50d87 */ (T_MASK ^ 0x0b2af278) +#define T28 0x455a14ed +#define T29 /* 0xa9e3e905 */ (T_MASK ^ 0x561c16fa) +#define T30 /* 0xfcefa3f8 */ (T_MASK ^ 0x03105c07) +#define T31 0x676f02d9 +#define T32 /* 0x8d2a4c8a */ (T_MASK ^ 0x72d5b375) +#define T33 /* 0xfffa3942 */ (T_MASK ^ 0x0005c6bd) +#define T34 /* 0x8771f681 */ (T_MASK ^ 0x788e097e) +#define T35 0x6d9d6122 +#define T36 /* 0xfde5380c */ (T_MASK ^ 0x021ac7f3) +#define T37 /* 0xa4beea44 */ (T_MASK ^ 0x5b4115bb) +#define T38 0x4bdecfa9 +#define T39 /* 0xf6bb4b60 */ (T_MASK ^ 0x0944b49f) +#define T40 /* 0xbebfbc70 */ (T_MASK ^ 0x4140438f) +#define T41 0x289b7ec6 +#define T42 /* 0xeaa127fa */ (T_MASK ^ 0x155ed805) +#define T43 /* 0xd4ef3085 */ (T_MASK ^ 0x2b10cf7a) +#define T44 0x04881d05 +#define T45 /* 0xd9d4d039 */ (T_MASK ^ 0x262b2fc6) +#define T46 /* 0xe6db99e5 */ (T_MASK ^ 0x1924661a) +#define T47 0x1fa27cf8 +#define T48 /* 0xc4ac5665 */ (T_MASK ^ 0x3b53a99a) +#define T49 /* 0xf4292244 */ (T_MASK ^ 0x0bd6ddbb) +#define T50 0x432aff97 +#define T51 /* 0xab9423a7 */ (T_MASK ^ 0x546bdc58) +#define T52 /* 0xfc93a039 */ (T_MASK ^ 0x036c5fc6) +#define T53 0x655b59c3 +#define T54 /* 0x8f0ccc92 */ (T_MASK ^ 0x70f3336d) +#define T55 /* 0xffeff47d */ (T_MASK ^ 0x00100b82) +#define T56 /* 0x85845dd1 */ (T_MASK ^ 0x7a7ba22e) +#define T57 0x6fa87e4f +#define T58 /* 0xfe2ce6e0 */ (T_MASK ^ 0x01d3191f) +#define T59 /* 0xa3014314 */ (T_MASK ^ 0x5cfebceb) +#define T60 0x4e0811a1 +#define T61 /* 0xf7537e82 */ (T_MASK ^ 0x08ac817d) +#define T62 /* 0xbd3af235 */ (T_MASK ^ 0x42c50dca) +#define T63 0x2ad7d2bb +#define T64 /* 0xeb86d391 */ (T_MASK ^ 0x14792c6e) + + +static void +md5_process(md5_state_t *pms, const md5_byte_t *data /*[64]*/) +{ + md5_word_t + a = pms->abcd[0], b = pms->abcd[1], + c = pms->abcd[2], d = pms->abcd[3]; + md5_word_t t; +#if BYTE_ORDER > 0 + /* Define storage only for big-endian CPUs. */ + md5_word_t X[16]; +#else + /* Define storage for little-endian or both types of CPUs. */ + md5_word_t xbuf[16]; + const md5_word_t *X; +#endif + + { +#if BYTE_ORDER == 0 + /* + * Determine dynamically whether this is a big-endian or + * little-endian machine, since we can use a more efficient + * algorithm on the latter. + */ + static const int w = 1; + + if (*((const md5_byte_t *)&w)) /* dynamic little-endian */ +#endif +#if BYTE_ORDER <= 0 /* little-endian */ + { + /* + * On little-endian machines, we can process properly aligned + * data without copying it. + */ + if (!((data - (const md5_byte_t *)0) & 3)) { + /* data are properly aligned */ + X = (const md5_word_t *)data; + } else { + /* not aligned */ + memcpy(xbuf, data, 64); + X = xbuf; + } + } +#endif +#if BYTE_ORDER == 0 + else /* dynamic big-endian */ +#endif +#if BYTE_ORDER >= 0 /* big-endian */ + { + /* + * On big-endian machines, we must arrange the bytes in the + * right order. + */ + const md5_byte_t *xp = data; + int i; + +# if BYTE_ORDER == 0 + X = xbuf; /* (dynamic only) */ +# else +# define xbuf X /* (static only) */ +# endif + for (i = 0; i < 16; ++i, xp += 4) + xbuf[i] = xp[0] + (xp[1] << 8) + (xp[2] << 16) + (xp[3] << 24); + } +#endif + } + +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) + + /* Round 1. */ + /* Let [abcd k s i] denote the operation + a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */ +#define F(x, y, z) (((x) & (y)) | (~(x) & (z))) +#define SET(a, b, c, d, k, s, Ti)\ + t = a + F(b,c,d) + X[k] + Ti;\ + a = ROTATE_LEFT(t, s) + b + /* Do the following 16 operations. */ + SET(a, b, c, d, 0, 7, T1); + SET(d, a, b, c, 1, 12, T2); + SET(c, d, a, b, 2, 17, T3); + SET(b, c, d, a, 3, 22, T4); + SET(a, b, c, d, 4, 7, T5); + SET(d, a, b, c, 5, 12, T6); + SET(c, d, a, b, 6, 17, T7); + SET(b, c, d, a, 7, 22, T8); + SET(a, b, c, d, 8, 7, T9); + SET(d, a, b, c, 9, 12, T10); + SET(c, d, a, b, 10, 17, T11); + SET(b, c, d, a, 11, 22, T12); + SET(a, b, c, d, 12, 7, T13); + SET(d, a, b, c, 13, 12, T14); + SET(c, d, a, b, 14, 17, T15); + SET(b, c, d, a, 15, 22, T16); +#undef SET + + /* Round 2. */ + /* Let [abcd k s i] denote the operation + a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */ +#define G(x, y, z) (((x) & (z)) | ((y) & ~(z))) +#define SET(a, b, c, d, k, s, Ti)\ + t = a + G(b,c,d) + X[k] + Ti;\ + a = ROTATE_LEFT(t, s) + b + /* Do the following 16 operations. */ + SET(a, b, c, d, 1, 5, T17); + SET(d, a, b, c, 6, 9, T18); + SET(c, d, a, b, 11, 14, T19); + SET(b, c, d, a, 0, 20, T20); + SET(a, b, c, d, 5, 5, T21); + SET(d, a, b, c, 10, 9, T22); + SET(c, d, a, b, 15, 14, T23); + SET(b, c, d, a, 4, 20, T24); + SET(a, b, c, d, 9, 5, T25); + SET(d, a, b, c, 14, 9, T26); + SET(c, d, a, b, 3, 14, T27); + SET(b, c, d, a, 8, 20, T28); + SET(a, b, c, d, 13, 5, T29); + SET(d, a, b, c, 2, 9, T30); + SET(c, d, a, b, 7, 14, T31); + SET(b, c, d, a, 12, 20, T32); +#undef SET + + /* Round 3. */ + /* Let [abcd k s t] denote the operation + a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */ +#define H(x, y, z) ((x) ^ (y) ^ (z)) +#define SET(a, b, c, d, k, s, Ti)\ + t = a + H(b,c,d) + X[k] + Ti;\ + a = ROTATE_LEFT(t, s) + b + /* Do the following 16 operations. */ + SET(a, b, c, d, 5, 4, T33); + SET(d, a, b, c, 8, 11, T34); + SET(c, d, a, b, 11, 16, T35); + SET(b, c, d, a, 14, 23, T36); + SET(a, b, c, d, 1, 4, T37); + SET(d, a, b, c, 4, 11, T38); + SET(c, d, a, b, 7, 16, T39); + SET(b, c, d, a, 10, 23, T40); + SET(a, b, c, d, 13, 4, T41); + SET(d, a, b, c, 0, 11, T42); + SET(c, d, a, b, 3, 16, T43); + SET(b, c, d, a, 6, 23, T44); + SET(a, b, c, d, 9, 4, T45); + SET(d, a, b, c, 12, 11, T46); + SET(c, d, a, b, 15, 16, T47); + SET(b, c, d, a, 2, 23, T48); +#undef SET + + /* Round 4. */ + /* Let [abcd k s t] denote the operation + a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */ +#define I(x, y, z) ((y) ^ ((x) | ~(z))) +#define SET(a, b, c, d, k, s, Ti)\ + t = a + I(b,c,d) + X[k] + Ti;\ + a = ROTATE_LEFT(t, s) + b + /* Do the following 16 operations. */ + SET(a, b, c, d, 0, 6, T49); + SET(d, a, b, c, 7, 10, T50); + SET(c, d, a, b, 14, 15, T51); + SET(b, c, d, a, 5, 21, T52); + SET(a, b, c, d, 12, 6, T53); + SET(d, a, b, c, 3, 10, T54); + SET(c, d, a, b, 10, 15, T55); + SET(b, c, d, a, 1, 21, T56); + SET(a, b, c, d, 8, 6, T57); + SET(d, a, b, c, 15, 10, T58); + SET(c, d, a, b, 6, 15, T59); + SET(b, c, d, a, 13, 21, T60); + SET(a, b, c, d, 4, 6, T61); + SET(d, a, b, c, 11, 10, T62); + SET(c, d, a, b, 2, 15, T63); + SET(b, c, d, a, 9, 21, T64); +#undef SET + + /* Then perform the following additions. (That is increment each + of the four registers by the value it had before this block + was started.) */ + pms->abcd[0] += a; + pms->abcd[1] += b; + pms->abcd[2] += c; + pms->abcd[3] += d; +} + +void +md5_init(md5_state_t *pms) +{ + pms->count[0] = pms->count[1] = 0; + pms->abcd[0] = 0x67452301; + pms->abcd[1] = /*0xefcdab89*/ T_MASK ^ 0x10325476; + pms->abcd[2] = /*0x98badcfe*/ T_MASK ^ 0x67452301; + pms->abcd[3] = 0x10325476; +} + +void +md5_append(md5_state_t *pms, const md5_byte_t *data, int nbytes) +{ + const md5_byte_t *p = data; + int left = nbytes; + int offset = (pms->count[0] >> 3) & 63; + md5_word_t nbits = (md5_word_t)(nbytes << 3); + + if (nbytes <= 0) + return; + + /* Update the message length. */ + pms->count[1] += nbytes >> 29; + pms->count[0] += nbits; + if (pms->count[0] < nbits) + pms->count[1]++; + + /* Process an initial partial block. */ + if (offset) { + int copy = (offset + nbytes > 64 ? 64 - offset : nbytes); + + memcpy(pms->buf + offset, p, copy); + if (offset + copy < 64) + return; + p += copy; + left -= copy; + md5_process(pms, pms->buf); + } + + /* Process full blocks. */ + for (; left >= 64; p += 64, left -= 64) + md5_process(pms, p); + + /* Process a final partial block. */ + if (left) + memcpy(pms->buf, p, left); +} + +void +md5_finish(md5_state_t *pms, md5_byte_t digest[16]) +{ + static const md5_byte_t pad[64] = { + 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 + }; + md5_byte_t data[8]; + int i; + + /* Save the length before padding. */ + for (i = 0; i < 8; ++i) + data[i] = (md5_byte_t)(pms->count[i >> 2] >> ((i & 3) << 3)); + /* Pad to 56 bytes mod 64. */ + md5_append(pms, pad, ((55 - (pms->count[0] >> 3)) & 63) + 1); + /* Append the length. */ + md5_append(pms, data, 8); + for (i = 0; i < 16; ++i) + digest[i] = (md5_byte_t)(pms->abcd[i >> 2] >> ((i & 3) << 3)); +} diff --git a/utils/md5.h b/utils/md5.h new file mode 100644 index 0000000..f944245 --- /dev/null +++ b/utils/md5.h @@ -0,0 +1,91 @@ +/* + Copyright (C) 1999, 2002 Aladdin Enterprises. All rights reserved. + + This software is provided 'as-is', without any express or implied + warranty. In no event will the authors be held liable for any damages + arising from the use of this software. + + Permission is granted to anyone to use this software for any purpose, + including commercial applications, and to alter it and redistribute it + freely, subject to the following restrictions: + + 1. The origin of this software must not be misrepresented; you must not + claim that you wrote the original software. If you use this software + in a product, an acknowledgment in the product documentation would be + appreciated but is not required. + 2. Altered source versions must be plainly marked as such, and must not be + misrepresented as being the original software. + 3. This notice may not be removed or altered from any source distribution. + + L. Peter Deutsch + ghost@aladdin.com + + */ +/* $Id: md5.h 15572 2010-06-15 17:23:44Z patrick $ */ +/* + Independent implementation of MD5 (RFC 1321). + + This code implements the MD5 Algorithm defined in RFC 1321, whose + text is available at + http://www.ietf.org/rfc/rfc1321.txt + The code is derived from the text of the RFC, including the test suite + (section A.5) but excluding the rest of Appendix A. It does not include + any code or documentation that is identified in the RFC as being + copyrighted. + + The original and principal author of md5.h is L. Peter Deutsch + <ghost@aladdin.com>. Other authors are noted in the change history + that follows (in reverse chronological order): + + 2002-04-13 lpd Removed support for non-ANSI compilers; removed + references to Ghostscript; clarified derivation from RFC 1321; + now handles byte order either statically or dynamically. + 1999-11-04 lpd Edited comments slightly for automatic TOC extraction. + 1999-10-18 lpd Fixed typo in header comment (ansi2knr rather than md5); + added conditionalization for C++ compilation from Martin + Purschke <purschke@bnl.gov>. + 1999-05-03 lpd Original version. + */ + +#ifndef md5_INCLUDED +# define md5_INCLUDED + +/* + * This package supports both compile-time and run-time determination of CPU + * byte order. If ARCH_IS_BIG_ENDIAN is defined as 0, the code will be + * compiled to run only on little-endian CPUs; if ARCH_IS_BIG_ENDIAN is + * defined as non-zero, the code will be compiled to run only on big-endian + * CPUs; if ARCH_IS_BIG_ENDIAN is not defined, the code will be compiled to + * run on either big- or little-endian CPUs, but will run slightly less + * efficiently on either one than if ARCH_IS_BIG_ENDIAN is defined. + */ + +typedef unsigned char md5_byte_t; /* 8-bit byte */ +typedef unsigned int md5_word_t; /* 32-bit word */ + +/* Define the state of the MD5 Algorithm. */ +typedef struct md5_state_s { + md5_word_t count[2]; /* message length in bits, lsw first */ + md5_word_t abcd[4]; /* digest buffer */ + md5_byte_t buf[64]; /* accumulate block */ +} md5_state_t; + +//#ifdef __cplusplus +//extern "C" +//{ +//#endif + +/* Initialize the algorithm. */ +void md5_init(md5_state_t *pms); + +/* Append a string to the message. */ +void md5_append(md5_state_t *pms, const md5_byte_t *data, int nbytes); + +/* Finish the message and return the digest. */ +void md5_finish(md5_state_t *pms, md5_byte_t digest[16]); + +//#ifdef __cplusplus +//} /* end extern "C" */ +//#endif + +#endif /* md5_INCLUDED */ diff --git a/utils/plist.c b/utils/plist.c new file mode 100644 index 0000000..daca93c --- /dev/null +++ b/utils/plist.c @@ -0,0 +1,151 @@ +#include "../stdafx.h" +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include "plist.h" + +/* + * A plist is a double-linked list of key-value pairs + * It can be circular or not. + */ + +/* + * This is a node in a plist + */ +struct plist_node { + void *pn_key; + void *pn_value; + struct plist_node *pn_next; + struct plist_node *pn_prev; +}; + +/* + * Adds a new entry into a plist. + * if !*root it creates a node where prev and next point to itself + * else, inserts itself in the list before *root + * returns 1 on success, 0 on NOMEM failure. + */ +int +plist_add(void *k, void *v, plist_node_t **root) +{ + plist_node_t *n; + + if (!(n = malloc(sizeof (*n)))) + return 0; + n->pn_key = k; + n->pn_value = v; + if (!*root) { + n->pn_next = n; + n->pn_prev = n; + *root = n; + } else { + n->pn_prev = (*root)->pn_prev; + n->pn_next = (*root); + (*root)->pn_prev->pn_next = n; + (*root)->pn_prev = n; + } + return 1; +} + +/* + * traverse list until cur == *root or cur == 0, freeing each node + * (list could be either circular or not) + * note that the key and value pointers are still valid. + */ +void +plist_clear(plist_node_t **root) +{ + plist_node_t *cur; + plist_node_t *fr; + + cur = *root; + while (cur) { + fr = cur; + cur = cur->pn_next; + free(fr); fr = NULL; + if (cur == *root) { + *root = NULL; + return; + } + } +} + +/* + * removes a node from a plist where the key pointer == k + * if ov is not null, it will point to the old value from the removed node + * This only removes the 1st occurance of k. + * returns 1 on success, 0 if k was not in the list + */ +int +plist_remove(void *k, plist_node_t **rootp, void **ov) +{ + plist_node_t *cur; + + cur = *rootp; + while (cur) { + if (cur->pn_key == k) { + if (ov) + *ov = cur->pn_value; + cur->pn_prev->pn_next = cur->pn_next; + cur->pn_next->pn_prev = cur->pn_prev; + if (cur->pn_next == cur) + *rootp = NULL; + else if (*rootp == cur) + *rootp = cur->pn_next; + free(cur); cur = NULL; + return 1; + } + cur = cur->pn_next; + if (cur == *rootp) + return 0; + } + return 0; +} + +/* + * finds k in plist. + * if ov != 0, it will be set to the value pointer + * returns 1 when the key is found, 0 if not found. + */ +int +plist_contains(void *k, plist_node_t *root, void **ov) +{ + plist_node_t *cur; + + cur = root; + while (cur) { + if (cur->pn_key == k) { + if (ov) + *ov = cur->pn_value; + return 1; + } + cur = cur->pn_next; + if (cur == root) + return 0; + } + return 0; +} + +/* + * traverses the plist from start, until we get back to start or next==0 + * runs func with key, val, arg. + * if func returns 0, stops traversing and returns 0 + * else returns 1 for success + */ +int +plist_walk(plist_node_t *start, int (*func)(const void *k, const void *v, + void *arg), void *arg) +{ + plist_node_t *cur; + int res; + + cur = start; + while (cur) { + if (!(res = func(cur->pn_key, cur->pn_value, arg))) + return res; + cur = cur->pn_next; + if (cur == start) + return 1; + } + return 1; +} diff --git a/utils/plist.h b/utils/plist.h new file mode 100644 index 0000000..52207a7 --- /dev/null +++ b/utils/plist.h @@ -0,0 +1,13 @@ +#ifndef _PLIST_H_ +#define _PLIST_H_ + +typedef struct plist_node plist_node_t; + +int plist_contains(void *k, plist_node_t *root, void **nodeval); +int plist_remove(void *k, plist_node_t **root, void **ov); +int plist_add(void *k, void *v, plist_node_t **root); +void plist_clear(plist_node_t **root); +int plist_walk(plist_node_t *start, int(*func)(const void *k, const void *v, + void *arg), void *arg); + +#endif diff --git a/utils/ptree.c b/utils/ptree.c new file mode 100644 index 0000000..f632e78 --- /dev/null +++ b/utils/ptree.c @@ -0,0 +1,460 @@ +#include "../stdafx.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> +#include "ptree.h" + +//#define VERIFY_TREE + +struct ptree_node { + void *pn_value; + struct ptree_node *pn_parent; + struct ptree_node *pn_left; + struct ptree_node *pn_right; +}; + +static int +_walk_to(void *v, + struct ptree_node **startp, + struct ptree_node ***pp, + int (*cmp)(const void *v1, const void *v2)) +{ + struct ptree_node **nextp; + int c = -1; + + nextp = startp; + while (*nextp) + { + c = cmp(v, (*nextp)->pn_value); + *startp = *nextp; + if (c == 0) + break; + if (c < 0) + nextp = &(*nextp)->pn_left; + else + nextp = &(*nextp)->pn_right; + if (pp) + *pp = nextp; + } + + return c; +} + + +static ptree_walk_res_t +_visit(struct ptree_node *pn, + int level, + void *arg1, + void *arg2) +{ + ptree_walk_res_t (*func)(const void *, int, void *, void *) = arg1; + + return func(pn->pn_value, level, arg2, pn); +} + +static ptree_node_t * +_find_min(ptree_node_t *pn, + int *levelp) +{ + while (pn->pn_left) + { + pn = pn->pn_left; + if (levelp) + (*levelp)++; + } + return pn; +} + +static ptree_node_t * +_find_succ(ptree_node_t *pn, + int *levelp) +{ + if (pn->pn_right) + { + pn = pn->pn_right; + if (levelp) + (*levelp)++; + while (pn->pn_left) + { + pn = pn->pn_left; + if (levelp) + (*levelp)++; + } + } + else + { + while (pn->pn_parent && pn->pn_parent->pn_right == pn) + { + pn = pn->pn_parent; + if (levelp) + (*levelp)--; + } + pn = pn->pn_parent; + if (levelp) + (*levelp)--; + } + + return pn; +} + +static int +_walk_int(struct ptree_node *pn, + ptree_order_t order, + int level, + ptree_walk_res_t (*func)(struct ptree_node *, int level, void *, void *), + void *arg1, + void *arg2) +{ + ptree_walk_res_t res; + ptree_node_t *next; + + if (!pn) + return PTREE_WALK_CONTINUE; + + if (order == PTREE_INORDER) + { + int nlevel; + + pn = _find_min(pn, &level); + while (pn) + { + nlevel = level; + next = _find_succ(pn, &nlevel); + if ((res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE) + return res; + level = nlevel; + if (level < 0) + level = 0; + pn = next; + } + return PTREE_WALK_CONTINUE; + } + if (order == PTREE_PREORDER && (res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE) + return res; + if ((res = _walk_int(pn->pn_left, order, level + 1, func, arg1, arg2)) != PTREE_WALK_CONTINUE) + return res; + if ((res = _walk_int(pn->pn_right, order, level + 1, func, arg1, arg2)) != PTREE_WALK_CONTINUE) + return res; + if (order == PTREE_POSTORDER && (res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE) + return res; + return PTREE_WALK_CONTINUE; +} + +#ifdef VERIFY_TREE +static ptree_walk_res_t +_count(struct ptree_node *pn, + int level, + void *arg1, + void *arg2) +{ + int *counter = arg1; + (*counter)++; + return PTREE_WALK_CONTINUE; +} + +//counts the number of nodes +static int +_count_nodes(ptree_node_t **rootp) +{ + int counter = 0; + _walk_int(*rootp, PTREE_INORDER, 0, _count, &counter, 0); + return counter; +} + +static ptree_walk_res_t +_verify_node(struct ptree_node *pn, + int level, + void *arg1, + void *arg2) +{ + int (*cmp)(const void *v1, const void *v2) = arg1; + struct ptree_node **prev_pn_p = (struct ptree_node **)arg2; + struct ptree_node *prev_pn = *prev_pn_p; + + if(pn->pn_left != NULL && pn->pn_left->pn_parent != pn) + return PTREE_WALK_STOP; + if(pn->pn_right != NULL && pn->pn_right->pn_parent != pn) + return PTREE_WALK_STOP; + + if(prev_pn != NULL) + { + //this value should always be greater then the last value + if(cmp(pn->pn_value, prev_pn->pn_value) <= 0) + return PTREE_WALK_STOP; + } + *prev_pn_p = pn; + + return PTREE_WALK_CONTINUE; +} + +//static int +//pdecmp(const void *sv, const void *dv) +//{ +// int res; +// +// char *str1 = *(char **)sv; +// char *str2 = *(char **)dv; +// +// res = strcmp(str1, str2); +// +// if(res <= 0) +// return res; +// +// return res; +//} + +//Verifies that the tree is a valid Binary search tree +static int +_verify_tree(ptree_node_t **rootp, int (*cmp)(const void *v1, const void *v2)) +{ + struct ptree_node *prev_pn = NULL; + if(_walk_int(*rootp, PTREE_INORDER, 0, _verify_node, cmp, &prev_pn) == PTREE_WALK_STOP) + return 0; + return 1; +} +#endif + +static void +_remove_node(ptree_node_t **rootp, + ptree_node_t *pn, + void **oldval) +{ + ptree_node_t **pp; + ptree_node_t **predp; + ptree_node_t *pred; + +#ifdef VERIFY_TREE + int countStart = _count_nodes(rootp), countEnd=0; +#endif + + //Find pn in the tree + if (!pn->pn_parent) + { + assert(rootp && pn == *rootp); + pp = rootp; + } + else + { + if (pn->pn_parent->pn_left == pn) + pp = &pn->pn_parent->pn_left; + else + pp = &pn->pn_parent->pn_right; + } + + //pp should now point at the location where pn is stored in the tree + assert(pp); + + //Best case - only one child, on no children, just remove as in a list + if (!pn->pn_left) + { + *pp = pn->pn_right; + if (pn->pn_right) + pn->pn_right->pn_parent = pn->pn_parent; + } + else if (!pn->pn_right) + { + *pp = pn->pn_left; + if (pn->pn_left) + pn->pn_left->pn_parent = pn->pn_parent; + } + + //Worst case: pn contains both left and right children + else + { + for (predp = &pn->pn_left; (*predp)->pn_right; ) + predp = &(*predp)->pn_right; + pred = *predp; + + //pred either has a left child or no child + if (pred->pn_parent->pn_left == pred) + pred->pn_parent->pn_left = pred->pn_left; + else + pred->pn_parent->pn_right = pred->pn_left; + if(pred->pn_left) + pred->pn_left->pn_parent = pred->pn_parent; + + *pp = pred; + + pred->pn_parent = pn->pn_parent; + pred->pn_left = pn->pn_left; + pred->pn_right = pn->pn_right; + + if (pn->pn_left) + pn->pn_left->pn_parent = pred; + pn->pn_right->pn_parent = pred; + } + + //Return the value of the removed node + if (oldval) + *oldval = pn->pn_value; + + free(pn); + +#ifdef VERIFY_TREE + countEnd = _count_nodes(rootp); + countStart--; + assert(countEnd == countStart); +#endif +} + +int +ptree_inorder_walk_remove(ptree_node_t **rootp, + void **oldval, + void *pn, + int (*cmp)(const void *v1, const void *v2)) +{ + assert(pn); + if (!pn) + return 0; +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + _remove_node(rootp, pn, oldval); +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + return 1; +} + +ptree_walk_res_t +ptree_walk(ptree_node_t *start, + ptree_order_t order, + ptree_walk_res_t (*func)(const void *v1, int level, void *arg, void *ptree_inorder_walking_remove_arg), + int (*cmp)(const void *v1, const void *v2), + void *arg) +{ +#ifdef VERIFY_TREE + ptree_node_t *start_p = start; + if(cmp != NULL) + assert(_verify_tree(&start_p, cmp)); +#endif + + return _walk_int((struct ptree_node *)start, order, 0, _visit, (void *)func, arg); +} + +ptree_walk_res_t +ptree_clear_func(struct ptree_node *pn, + int level, + void *arg1, + void *arg2) +{ + free(pn); pn = NULL; + + return PTREE_WALK_CONTINUE; +} + +void +ptree_clear(ptree_node_t **rootp) +{ + _walk_int(*rootp, PTREE_POSTORDER, 0, ptree_clear_func, 0, 0); + *rootp = 0; +} + +int +ptree_remove(void *v, + ptree_node_t **rootp, + int (*cmp)(const void *v1, const void *v2), + void **oldval) +{ + struct ptree_node *cur; + +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + + cur = *rootp; + if (_walk_to(v, &cur, NULL, cmp) != 0) + return 0; + _remove_node(rootp, cur, oldval); + +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + + return 1; +} + +int +ptree_replace(void *v, + ptree_node_t **rootp, + int (*cmp)(const void *v1, const void *v2), + void **oldval) +{ + struct ptree_node **parentpp; + struct ptree_node *parentp; + struct ptree_node *pn; + int c; + +#ifdef VERIFY_TREE + int countStart = _count_nodes(rootp), countEnd=0; +#endif + + parentp = *rootp; + parentpp = rootp; + +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + + //if we find v in the tree, replace it + if ((c = _walk_to(v, &parentp, &parentpp, cmp)) == 0) + { + if (oldval) + *oldval = parentp->pn_value; + parentp->pn_value = v; + +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + +#ifdef VERIFY_TREE + countEnd = _count_nodes(rootp); + assert(countEnd == countStart); +#endif + + return 1; + } + + //otherwise, add it to the tree + if (!(pn = malloc(sizeof (*pn)))) + return 0; + + memset(pn, 0, sizeof (*pn)); + pn->pn_value = v; + pn->pn_parent = parentp; + *parentpp = pn; + if (oldval) + *oldval = 0; + +#ifdef VERIFY_TREE + assert(_verify_tree(rootp, cmp)); +#endif + +#ifdef VERIFY_TREE + countEnd = _count_nodes(rootp); + countStart++; + assert(countEnd == countStart); +#endif + + return 1; +} + +int +ptree_contains(void *v, + ptree_node_t *parentp, + int (*cmp)(const void *v1, const void *v2), + void **nodeval) +{ + int c; + + if ((c = _walk_to(v, &parentp, NULL, cmp)) == 0) + { + if (nodeval) + *nodeval = parentp->pn_value; + return 1; + } + if (nodeval) + *nodeval = 0; + return 0; +}
\ No newline at end of file diff --git a/utils/ptree.h b/utils/ptree.h new file mode 100644 index 0000000..62166ac --- /dev/null +++ b/utils/ptree.h @@ -0,0 +1,33 @@ +#ifndef _PTREE_H_ +#define _PTREE_H_ + +typedef struct ptree_node ptree_node_t; + +typedef enum { + PTREE_PREORDER = 1, + PTREE_INORDER = 2, + PTREE_POSTORDER = 3 +} ptree_order_t; + +typedef enum { + PTREE_WALK_STOP = 0, + PTREE_WALK_CONTINUE = 1 +} ptree_walk_res_t; + +int ptree_contains(void *v, ptree_node_t *root, int(*)(const void *sv, + const void *tv), void **nodeval); +int ptree_remove(void *v, ptree_node_t **root, int(*)(const void *sv, + const void *tv), void **oltval); +int ptree_replace(void *v, ptree_node_t **root, int(*)(const void *sv, + const void *tv), void **oltval); +void ptree_clear(ptree_node_t **root); +ptree_walk_res_t +ptree_walk(ptree_node_t *start, + ptree_order_t order, + ptree_walk_res_t (*func)(const void *v1, int level, void *arg, void *ptree_inorder_walking_remove_arg), + int (*cmp)(const void *v1, const void *v2), + void *arg); +int ptree_inorder_walk_remove(ptree_node_t **rootp, void **oldval, void *piwra, + int (*cmp)(const void *v1, const void *v2)); + +#endif diff --git a/utils/utils.c b/utils/utils.c new file mode 100644 index 0000000..57611f2 --- /dev/null +++ b/utils/utils.c @@ -0,0 +1,1223 @@ +#include "../stdafx.h" +#include <ctype.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <regex.h> +#include <assert.h> +#if !defined(_WINDOWS) || defined(__CYGWIN__) +#include <fcntl.h> +#include <netdb.h> +#include <netinet/in.h> +//#include <arpa/inet.h> +#include <sys/poll.h> +#else +#include "wincompat.h" +#endif +#if defined(__CYGWIN__) || defined(__MINGW32_VERSION) +#include "getaddrinfo.h" +#endif +#ifndef _MSC_EXTENSIONS +#include <unistd.h> +#endif +#include "utils.h" + +#if defined(_MACOSX) || defined(_LINUX) +// Use IPv6 on Mac OS and Linux +#define _ENABLE_IPv6 +#endif + +/* character escaping */ +#define PASSTHRU(c) (isalnum((unsigned char)c)/* || c == ' '*/ || c == '.' || c == '/' || c == ':' || c == '%') + +#ifndef _WINDOWS +#define SET_ERRDESC(errdesc, errdesclen) (errdesc ? snprintf(errdesc, \ + errdesclen, "%s", strerror(errno)) : 0); +#else +#define SET_ERRDESC(errdesc, errdesclen) wsa_set_errdesc(errdesc, errdesclen); +#endif + +/* size of first buffer malloc; start small to exercise grow routines */ +#define FIRSTSIZE 128 + +int logging_enabled = FALSE; +#ifndef USE_PHIDGET21_LOGGING +static FILE *log_stream = 0; +static const char *log_pname = 0; +#endif + +#if defined(_WINDOWS) && !defined(_CYGWIN) +static void +wsa_set_errdesc(char *errdesc, int len) +{ + int err; + + if (!errdesc) + return; + switch (err = WSAGetLastError()) { + case 10038: + snprintf(errdesc, len, "Socket operation on non-socket"); + return; + case 10061: + snprintf(errdesc, len, "Connection refused"); + return; + default: + snprintf(errdesc, len, "WSA error %d", err); + return; + } +} +#endif + + +/* Modified to work properly on ALL systems, not just UNIX */ +int +pvasprintf(char **ret, const char *fmt, va_list ap) +{ + char *buf = NULL; + size_t bufsize = 0; + char *newbuf = NULL; + size_t nextsize = 0; + int outsize = 0; + + bufsize = 0; + for (;;) { + if (bufsize == 0) { + if ((buf = (char *)malloc(FIRSTSIZE)) == NULL) { + *ret = NULL; + return -1; + } + bufsize = 1; + } else if ((newbuf = (char *)realloc(buf, nextsize)) != NULL) { + buf = newbuf; + bufsize = nextsize; + } else { + free(buf); buf = NULL; + *ret = NULL; + return -1; + } + +#ifdef _WINDOWS + outsize = _vsnprintf(buf, bufsize, fmt, ap); +#else + { + va_list copy; + va_copy(copy, ap); + outsize = vsnprintf(buf, bufsize, fmt, copy); + va_end(copy); + } +#endif + + if (outsize == -1) { + /* Clear indication that output was truncated, but no + * clear indication of how big buffer needs to be, so + * simply double existing buffer size for next time. + */ + nextsize = (int)bufsize * 2; + + } else if (outsize == (int)bufsize) { + /* Output was truncated (since at least the \0 could + * not fit), but no indication of how big the buffer + * needs to be, so just double existing buffer size + * for next time. + */ + nextsize = (int)bufsize * 2; + + } else if (outsize > (int)bufsize) { + /* Output was truncated, but we were told exactly how + * big the buffer needs to be next time. Add two chars + * to the returned size. One for the \0, and one to + * prevent ambiguity in the next case below. + */ + nextsize = outsize + 2; + + } else if (outsize == (int)bufsize - 1) { + /* This is ambiguous. May mean that the output string + * exactly fits, but on some systems the output string + * may have been trucated. We can't tell. + * Just double the buffer size for next time. + */ + nextsize = (int)bufsize * 2; + + } else { + /* Output was not truncated */ + break; + } + } + *ret = buf; + return (int)strlen(buf); +} + +int +pasprintf(char **ret, const char *fmt, ...) +{ + va_list args; + int outsize = 0; + + va_start(args, fmt); + outsize = pvasprintf(ret, fmt, args); + va_end(args); + + return outsize; +} + +int +pd_getline(char *buf, unsigned int bufsize, int *bufcur, + int *buflen, int(*readfunc)(int, void *, unsigned int, char *, + int), int(*closefunc)(int, char *, int), int readfd, char **line, + char *errdesc, int errlen) +{ + char *eol; + unsigned int srcsize; + int linelen; + int linesize = 1024; + + linelen = 0; + if (!(*line = malloc(linesize))) { + /* no memory */ + if (closefunc) + (void) closefunc(readfd, errdesc, errlen); + return 0; + } + **line = 0; + +top: + /* this loops until buf is empty, or we hit the end of a line */ + while (*bufcur < *buflen) { + + /* looking for eol - \n or \0 + * eol points to the line ending \0, or NULL if line continues. + * srcsize set to number of chars to copy into line. */ + if (!(eol = strchr(buf + *bufcur, '\n'))) + { + if (!(eol = memchr(buf + *bufcur, '\0', *buflen - *bufcur))) + { + /* couldn't find '\n' or '\0' */ + srcsize = *buflen - *bufcur; + } + else + { + /* found '\0' */ + srcsize = eol - buf - *bufcur + 1; + } + } + else + { + /* found '\n' */ + srcsize = eol - buf - *bufcur + 1; + /* change \n into \0 */ + *eol = 0; + } + + /* double size of *line until it's big enough for srcsize characters */ + while ((int)srcsize > (linesize - linelen)) + { + char *newline; + + linesize *= 2; + + if (!(newline = realloc(*line, linesize))) { + /* not enough memory */ + free(*line); + *line = NULL; + if (closefunc) + (void) closefunc(readfd, errdesc, errlen); + return 0; + } + + *line = newline; + } + + /* copy buf into line and modify pointers */ + memcpy(*line + linelen, buf + *bufcur, srcsize); + linelen += srcsize; + *bufcur += srcsize; + + /* Are we at the end of the string? */ + if (eol) + { + /* change the first \r into a \0 + * This handles when they send \r\n but not \n\r */ + if ((eol = strchr(*line, '\r')) != NULL) + *eol = 0; + + /* This is the (only) happy return from this function */ + return 1; + } + } //while (*bufcur < *buflen) + + /* we get here when there wasn't the end of a string in the buffer */ + *bufcur = 0; + /* read in some data */ + if ((*buflen = readfunc(readfd, buf, bufsize - 1, errdesc, errlen)) <= 0) + { + /* read either errored, or the socket is closed */ + free(*line); + *line = NULL; + if (closefunc) + (void) closefunc(readfd, errdesc, errlen); + return 0; + } + /* null terminate - so strchr knows when to stop */ + buf[*buflen] = 0; + /* go process it */ + goto top; +} + +/*int +pd_getline_simple(int fd, char **line) +{ +int bufcur = 0; +int buflen = 0; +char buf[2]; + +return pd_getline(buf, sizeof (buf), &bufcur, &buflen, pu_read, 0, fd, +line, 0, 0); +}*/ + +int +getmatchsub(const char *line, char **subp, const regmatch_t pmatch[], int n) +{ + int len; + + len = (pmatch[n].rm_so >= 0) ? pmatch[n].rm_eo - pmatch[n].rm_so : 0; + if (subp) { + if (len) { + if (!(*subp = malloc(len + 1))) + return len; + memcpy(*subp, line + pmatch[n].rm_so, len); + subp[0][len] = 0; + } else { + *subp = NULL; + } + } + + return len; +} + +static int waitForConnect(int s, int cancel) +{ + int err; + fd_set readFDs; + fd_set writeFDs; + fd_set errorFDs; + int selectResult; + int maxFD = s; + + FD_ZERO(&readFDs); + FD_ZERO(&writeFDs); + FD_ZERO(&errorFDs); + + // We always want the cancel socket in the read FD set. +#ifndef _WINDOWS + if (cancel >= 0) +#else + if (cancel != INVALID_SOCKET) +#endif + FD_SET(cancel, &readFDs); + FD_SET(s, &readFDs); + FD_SET(s, &writeFDs); + FD_SET(s, &errorFDs); + +#ifndef _WINDOWS + if (cancel >= 0 && cancel > s) +#else + if (cancel != INVALID_SOCKET && cancel > s) +#endif + maxFD = cancel; + + // Do the select, looping while we get EINTR errors. + err = 0; + do { +#ifndef _WINDOWS + selectResult = select(maxFD + 1, &readFDs, &writeFDs, NULL, NULL); +#else + //Windows reports a failed connect in errorFDs + selectResult = select(maxFD + 1, &readFDs, &writeFDs, &errorFDs, NULL); +#endif + + if (selectResult < 0) { +#ifndef _WINDOWS + err = errno; +#else + err = WSAGetLastError(); +#endif + } + } while (err == EINTR); + + if (err == 0) { + // We have an infinite timeout, so a result of 0 should be impossible, + // so assert that selectResult is positive. + assert(selectResult > 0); + + // Check for cancellation first. +#ifndef _WINDOWS + if (cancel >= 0) +#else + if (cancel != INVALID_SOCKET) +#endif + { + if ( FD_ISSET(cancel, &readFDs) ) { + err = ECANCELED; + } + } + } + + return err; +} + +int cancelConnect(int cancelSocket) +{ + int err; + ssize_t bytesWritten; + static const char kCancelMessage = 0; + + err = 0; + +#ifndef _WINDOWS + bytesWritten = write(cancelSocket, &kCancelMessage, sizeof(kCancelMessage)); +#else + bytesWritten = send(cancelSocket, &kCancelMessage, sizeof(kCancelMessage), MSG_NOSIGNAL); +#endif + if (bytesWritten < 0) { + err = errno; + } + return err; +} + +int CCONV +stream_server_connect(const char *dest, const char *svcname, int *fdp, int *cancelSocket, char *errdesc, int errdesclen) +{ + struct addrinfo hints, *res, *res0 = NULL; + int err, cancelled = 0; + SOCKET s = INVALID_SOCKET; + int tmpSock[2]; + int cancelRecvSocket = INVALID_SOCKET; +#ifdef _WINDOWS + u_long nNonBlocking = TRUE; +#endif +#ifdef _MACOSX + int opt; +#endif + + memset(&hints, 0, sizeof(hints)); + //hints.ai_family = AF_INET; + hints.ai_family = PF_UNSPEC; //any family (including IPV6) + hints.ai_socktype = SOCK_STREAM; +#ifndef WINCE + hints.ai_flags = AI_ADDRCONFIG; +#endif + + if ((err = getaddrinfo(dest, svcname, &hints, &res0)) != 0) { + if (errdesc) + snprintf(errdesc, errdesclen, "getaddrinfo: %s", gai_strerror(err)); + freeaddrinfo(res0); + return 0; + } + + //setup cancel socket + err = socketpair(AF_UNIX, SOCK_STREAM, 0, tmpSock); + if (err < 0) { + SET_ERRDESC(errdesc, errdesclen); + *cancelSocket = INVALID_SOCKET; + pu_log(PUL_WARN, 0, "Unable to create a cancel socket: %s",errdesc); + return 0; + } else { + *cancelSocket = tmpSock[0]; + cancelRecvSocket = tmpSock[1]; + } + + for (res = res0; res; res = res->ai_next) { + if(cancelled) + break; + + // sometimes on mac, we get 0.0.0.0 ??!! - just ignore it + // I think this is IPv6 - don't ignore... + //if(((struct sockaddr_in *)res->ai_addr)->sin_addr.s_addr == 0) + //{ + // continue; + //} + + s = socket(res->ai_family, res->ai_socktype, res->ai_protocol); +#ifndef _WINDOWS + if (s < 0) +#else + if (s == INVALID_SOCKET) +#endif + { + SET_ERRDESC(errdesc, errdesclen); + continue; + } + + //Make the socket non-blocking +#ifndef _WINDOWS + if (fcntl(s, F_SETFL, O_NONBLOCK) < 0) { + SET_ERRDESC(errdesc, errdesclen); + s = INVALID_SOCKET; + continue; + } +#else + if (ioctlsocket(s, FIONBIO, (u_long FAR *) & nNonBlocking)) + { + s = INVALID_SOCKET; + continue; + } +#endif + + if((err = connect(s, res->ai_addr, (int) res->ai_addrlen)) != 0) + { + //Connection in progress - wait for completion or cancelation +#ifndef _WINDOWS + if(errno == EINPROGRESS) +#else + err = WSAGetLastError(); + if(err == WSAEINPROGRESS || err == WSAEWOULDBLOCK) +#endif + { + err = waitForConnect(s, cancelRecvSocket); + + // Not cancelled, so must have either connected or failed. + // Check to see if we're connected by calling getpeername. + if (err == 0) { + socklen_t len = sizeof(struct sockaddr); + struct sockaddr name; + err = getpeername(s, &name, &len); + + // The connection failed. Get the error associated with + // the connection attempt. + if (err < 0) { + char tmpErr; +#ifdef _WINDOWS + err = WSAGetLastError(); +#endif + len = sizeof(tmpErr); + err = getsockopt(s, SOL_SOCKET, SO_ERROR, &tmpErr, &len); + if (err < 0) { +#ifdef _WINDOWS + err = WSAGetLastError(); +#else + err = errno; +#endif + } else { + assert(tmpErr != 0); + err = tmpErr; + } + } + //connection good + else + break; + } + //cancelled + else if(err==ECANCELED) + { + cancelled = 1; + } + +#ifdef _WINDOWS + WSASetLastError(err); +#else + errno = err; +#endif + } + //Error + SET_ERRDESC(errdesc, errdesclen); +#ifndef _WINDOWS + close(s); +#else + closesocket(s); +#endif + s = INVALID_SOCKET; + continue; + } + break; + } + + //cleanup cancel socket - not needed anymore + if (tmpSock[0] != -1) +#ifndef _WINDOWS + close(tmpSock[0]); +#else + closesocket(tmpSock[0]); +#endif + if (tmpSock[1] != -1) +#ifndef _WINDOWS + close(tmpSock[1]); +#else + closesocket(tmpSock[1]); +#endif + *cancelSocket = INVALID_SOCKET; + +#ifndef _WINDOWS + if (s < 0) +#else + if (s == INVALID_SOCKET) +#endif + { + SET_ERRDESC(errdesc, errdesclen); + freeaddrinfo(res0); + return 0; + } + +#ifdef _MACOSX + opt = 1; + setsockopt(s, SOL_SOCKET, SO_NOSIGPIPE, &opt, sizeof(opt)); +#endif + if (fdp) + *fdp = s; + freeaddrinfo(res0); + return 1; +} + + +#ifndef _ENABLE_IPv6 +/* +* Accepts a TCP connection on a given port and invokes the given +* callback to handle it. This is where the main server thread sits. +* IPv4 Version +*/ +int +stream_server_accept(int port, void(*clfunc)(int fd, const char *addr, + int port), char *errdesc, int errdesclen) +{ + struct sockaddr_in sin = { 0 }; + struct sockaddr_in cin = { 0 }; + const int opt = 1; + socklen_t cl; + char *addr; + int fd; + int s; + int errcount=0; + //#ifdef _WINDOWS + // u_long nNonBlocking = TRUE; + //#endif + + if (!(s = (int)socket(PF_INET, SOCK_STREAM, 0))) { + SET_ERRDESC(errdesc, errdesclen); + return 0; + } + setsockopt(s, SOL_SOCKET, SO_REUSEADDR, (void *)&opt, sizeof (opt)); +#ifdef _MACOSX + setsockopt(s, SOL_SOCKET, SO_NOSIGPIPE, (void *)&opt, sizeof (opt)); +#endif + sin.sin_family = AF_INET; + sin.sin_port = htons(port); + sin.sin_addr.s_addr = INADDR_ANY; + if (bind(s, (struct sockaddr *)&sin, sizeof (sin)) != 0) { + SET_ERRDESC(errdesc, errdesclen); + return 0; + } + if (listen(s, 5) != 0) { + SET_ERRDESC(errdesc, errdesclen); + return 0; + } + for (;;) { + cl = sizeof(cin); + while ((fd = (int)accept(s, (struct sockaddr *)&cin, &cl)) < 0 && + errno == EAGAIN) + ; + if (fd < 0) { + SET_ERRDESC(errdesc, errdesclen); + pu_log(PUL_WARN, 0, "Error in stream_server_accept: %s",errdesc); + if(errcount < 10) + { + SLEEP(50); + continue; + } + else + { + pu_log(PUL_CRIT, 0, "Too many errors in stream_server_accept, exiting."); + return 0; + } + } + errcount = 0; + setsockopt(fd, SOL_SOCKET, SO_KEEPALIVE, (void *)&opt, sizeof (opt)); + +#ifdef _MACOSX + // otherwise we get SIGPIPEs that aren't important + setsockopt(fd, SOL_SOCKET, SO_NOSIGPIPE, (void *)&opt, sizeof (opt)); +#endif + + addr = strdup(inet_ntoa(cin.sin_addr)); + clfunc(fd, addr, ntohs(cin.sin_port)); + free(addr); addr = NULL; + } + /*NOTREACHED*/ +} + +#else + +/* +* Accepts a TCP connection on a given port and invokes the given +* callback to handle it. This is where the main server thread sits. +* IPv6 version! - doesn't work with Windows yet... +*/ +int +stream_server_accept(int port, + void(*clfunc)(int fd, const char *addr,int port), + char *errdesc, + int errdesclen) +{ + struct addrinfo *ai, *runp; + struct addrinfo hints; + int e, nfds; + char portStr[20]; + struct pollfd *fds; + int opt; + + // Get a list of interfaces to Bind to + memset(&hints, '\0', sizeof(hints)); + hints.ai_flags = AI_PASSIVE | AI_ADDRCONFIG; + hints.ai_socktype = SOCK_STREAM; + //hints.ai_family = PF_UNSPEC; + + snprintf(portStr, 20, "%d", port); + if((e = getaddrinfo(NULL, portStr, &hints, &ai)) != 0) + { + (errdesc ? snprintf(errdesc, errdesclen, "getaddrinfo: %s", gai_strerror(e)) : 0); + return 0; + } + + // Malloc array + nfds = 0; + runp = ai; + while(runp) + { + nfds++; + runp = runp->ai_next; + } + fds = (struct pollfd *)malloc(nfds * sizeof(struct pollfd)); + + pu_log(PUL_INFO, 0, "Found %d interfaces to Bind to.", nfds); + + // Bind to interfaces + for(nfds = 0, runp = ai; runp; runp = runp->ai_next) + { + pu_log(PUL_INFO, 0, "Setting up interface %d: Family:%d, Socktype:%d, Protocol:%d", nfds, runp->ai_family, runp->ai_socktype, runp->ai_protocol); + + if((fds[nfds].fd = socket(runp->ai_family, runp->ai_socktype, runp->ai_protocol)) < 0) + { + pu_log(PUL_WARN, 0, "Error on socket: %s", strerror(errno)); + continue; + } + + fds[nfds].events = POLLIN; + opt = 1; + setsockopt(fds[nfds].fd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt)); +#ifdef _MACOSX + opt = 1; + setsockopt(fds[nfds].fd, SOL_SOCKET, SO_NOSIGPIPE, &opt, sizeof(opt)); +#endif + + if(bind(fds[nfds].fd, runp->ai_addr, runp->ai_addrlen) != 0) + { + if(errno != EADDRINUSE) + { + pu_log(PUL_WARN, 0, "Error on bind: %s", strerror(errno)); + continue; + } + else + close(fds[nfds].fd); + } + else //bind was successfull + { + if(listen(fds[nfds].fd, SOMAXCONN) != 0) + { + pu_log(PUL_WARN, 0, "Error on listen: %s", strerror(errno)); + continue; + } + else //listen was successfull + nfds++; + } + + } + freeaddrinfo(ai); + + // didn't bind to anything! + if(nfds == 0) + { + (errdesc ? snprintf(errdesc, errdesclen, "Couldn't bind to any interfaces!") : 0); + return 0; + } + + while(1) + { + if(poll(fds, nfds, -1) > 0) + { + int i; + for(i = 0; i < nfds; i++) + { + if(fds[i].revents & POLLIN) + { + struct sockaddr_storage rem; + socklen_t remlen = sizeof(rem); + int fd; + char addr[200]; + + while((fd = accept(fds[i].fd, (struct sockaddr *) &rem, &remlen)) < 0 && errno == EAGAIN); + + if(fd < 0) + { + SET_ERRDESC(errdesc, errdesclen); + return 0; + } + + opt = 1; + setsockopt(fd, SOL_SOCKET, SO_KEEPALIVE, (void *)&opt, sizeof (opt)); +#ifdef _MACOSX + opt = 1; + setsockopt(fd, SOL_SOCKET, SO_NOSIGPIPE, (void *)&opt, sizeof (opt)); +#endif + + (void)getnameinfo((struct sockaddr *)&rem, remlen, addr, sizeof(addr), NULL, 0, NI_NUMERICHOST); + clfunc(fd, addr, ntohs(((struct sockaddr_in *)&rem)->sin_port)); + } + } + } + } + /*NOTREACHED*/ +} +#endif + +int +pu_write(int fd, const void *buf, unsigned int len, char *errdesc, int edlen) +{ + //why a static mutex instead of a per-socket one??? + //Why a mutex at all?? I'm oging to disable and see what happens... + //static pthread_mutex_t *writelock = 0; + int res = 0; + int olen = len; +#ifdef _WINDOWS + int bytesSent = 0; + WSABUF DataBuf; +#endif + + if (fd == -1) + return len; + + pu_log(PUL_VERB, 0, "Sending: \"%s\"",(char *)buf); + + //if (!writelock) { + // if (!(writelock = malloc(sizeof (*writelock)))) + // return 0; + // pthread_mutex_init(writelock, NULL); + //} + //pthread_mutex_lock(writelock); + do { + if (res > 0) { +#ifdef _WINDOWS + (unsigned char *)buf += res; +#else + buf += res; +#endif + len -= res; + } + if (len) + { +tryagain: +#ifdef _WINDOWS + DataBuf.buf = (char *)buf; + DataBuf.len = len; + + res = WSASend(fd, &DataBuf, 1, &bytesSent, 0, NULL, NULL); + if(res) + res = -1; + else + res = bytesSent; +#else + res = send(fd, buf, len, MSG_NOSIGNAL); +#endif + //Error + if(res == -1) + { +#ifdef _WINDOWS + switch(WSAGetLastError()) + { + //non-blocking, try again + case WSAEWOULDBLOCK: + SLEEP(10); + goto tryagain; + //any other error, don't try again + default: + break; + } +#else + switch(errno) + { + //Interrupted, try again + case EINTR: + //non-blocking, try again + case EAGAIN: + SLEEP(10); + goto tryagain; + //any other error, don't try again + default: + break; + } +#endif + } + } + else + res = olen; + } while (len && res >= 0); + //pthread_mutex_unlock(writelock); + + if (res != olen) { + SET_ERRDESC(errdesc, edlen); + return 0; + } else + return 1; +} + +int +pu_read(int fd, void *buf, unsigned int len, char *errdesc, int edlen) +{ + int res=0; + if (fd == -1) + return 0; + +tryagain: + res = recv(fd, buf, len, 0); + //Error + if(res == -1) + { +#ifdef _WINDOWS + switch(WSAGetLastError()) + { + //non-blocking, try again + case WSAEWOULDBLOCK: + SLEEP(10); + goto tryagain; + //any other error, don't try again + default: + break; + } +#else + switch(errno) + { + //Interrupted, try again + case EINTR: + //non-blocking, try again + case EAGAIN: + SLEEP(10); + goto tryagain; + //any other error, don't try again + default: + break; + } +#endif + } + if (res <= 0) { + SET_ERRDESC(errdesc, edlen); + return 0; + } else + { + pu_log(PUL_VERB,0,"Recieved: \"%s\"", (char *)buf); + return res; + } +} + +int +pu_close(int fd, char *errdesc, int edlen) +{ + int res=0; + if(fd == -1) return 0; +#ifndef _WINDOWS + res = close(fd); +#else + res = closesocket(fd); +#endif + SET_ERRDESC(errdesc, edlen); + return res; +} + +// We want to use phidget21 logging not utils.c logging +#ifndef USE_PHIDGET21_LOGGING +static const char * +pu_log_level_str(pu_log_level_t l) +{ + switch (l) { + case PUL_ERR: + return "ERR"; + case PUL_CRIT: + return "CRIT"; + case PUL_WARN: + return "WARN"; + case PUL_INFO: + return "INFO"; + case PUL_DEBUG: + return "DEBUG"; + case PUL_VERB: + return "VERBOSE"; + } + return "???"; +} + +void +pu_log_stream(FILE *str) +{ + log_stream = str; +} + +void +pu_log_pname(const char *newname) +{ + log_pname = newname; +} + +void +pu_log(pu_log_level_t l, int s, const char *fmt, ...) +{ + static pthread_mutex_t logLock; + static int logLockInitialized = FALSE; + va_list va; + + if(!logLockInitialized) + { + pthread_mutex_init(&logLock, NULL); + logLockInitialized = TRUE; + } + pthread_mutex_lock(&logLock); + +#ifndef DEBUG + if(logging_enabled) +#endif + { +#ifdef WINCE + if (!log_stream) + log_stream = stdout; + fprintf(log_stream, "%s%s%d/%s ", log_pname ? log_pname : "", + log_pname ? " " : "", s, pu_log_level_str(l)); + va_start(va, fmt); + vfprintf(log_stream, fmt, va); + va_end(va); + fprintf(log_stream, "\n"); + fflush(log_stream); +#else + char date[50]; + struct tm *tm; + time_t t; + + if (!log_stream) + log_stream = stdout; + + time(&t); + tm = localtime(&t); + if (!strftime(date, sizeof (date), "%c", tm)) + strncpy(date, "?", sizeof (date)); + fprintf(log_stream, "%s %s%s%d/%s ", date, log_pname ? log_pname : + "", log_pname ? " " : "", s, pu_log_level_str(l)); + va_start(va, fmt); + vfprintf(log_stream, fmt, va); + va_end(va); + fprintf(log_stream, "\n"); + fflush(log_stream); +#endif + } + pthread_mutex_unlock(&logLock); +} +#else +void +pu_log(pu_log_level_t l, int s, const char *fmt, ...) +{ + CPhidgetLog_level level; + char msg[2048], id[10]; + va_list va; + + switch(l) + { + case PUL_ERR: + level = PHIDGET_LOG_ERROR; + break; + case PUL_CRIT: + level = PHIDGET_LOG_CRITICAL; + break; + case PUL_WARN: + level = PHIDGET_LOG_WARNING; + break; + case PUL_INFO: + level = PHIDGET_LOG_INFO; + break; + case PUL_DEBUG: + level = PHIDGET_LOG_DEBUG; + break; + case PUL_VERB: + default: + level = PHIDGET_LOG_VERBOSE; + break; + } + + va_start(va, fmt); +#ifdef WINCE + vsprintf(msg, fmt, va); +#else + vsnprintf(msg, 2048, fmt, va); +#endif + va_end(va); + + snprintf(id, 10, "%d", s); + CPhidget_log(level, id, msg); +} +#endif + +int +hexval(unsigned char c) +{ + if (isdigit(c)) + return c - '0'; + c = tolower(c); + if (c <= 'f' && c >= 'a') + return c - 'a' + 10; + return -1; +} + +int +unescape(const char *src, char **dstp, unsigned int *dlenp) +{ + char *dst; + size_t slen; + size_t dlen; + size_t i; + + for (i = 0, dlen = 0, slen = strlen(src); i < slen; i++, dlen++) + if (src[i] == '\\') + i += 3; + + if (!(dst = malloc(dlen + 1))) + return 0; + for (i = 0, dlen = 0, slen = strlen(src); i < slen; i++, dlen++) + if (src[i] == '\\') { + dst[dlen] = hexval((unsigned)src[i + 2]) * 16 + + hexval((unsigned)src[i + 3]); + i += 3; + } else + dst[dlen] = src[i]; + if (dlenp) + *dlenp = (unsigned int)dlen; + dst[dlen] = 0; + + *dstp = dst; + return 1; +} + +static unsigned char +hexchar(unsigned char c) +{ + if (c > 16) + return 'f'; + if (c >= 10) + return c - 10 + 'a'; + return c + '0'; +} + + +int +escape2(const char *src, unsigned int slen, char **dstp, int escbacks) +{ + char *dst; + size_t dlen; + size_t i; + + if (!slen) + slen = (int)strlen(src); + for (i = 0, dlen = 0; i < slen; i++) + if (PASSTHRU(src[i])) + dlen++; + else + if(escbacks) + dlen += 6; + else + dlen += 4; + + if (!(dst = malloc(dlen + 1))) + return 0; + for (i = 0, dlen = 0; i < slen; i++) + if (!PASSTHRU(src[i])) { + dst[dlen++] = '\\'; + if(escbacks) + dst[dlen++] = '\\'; + dst[dlen++] = 'x'; + dst[dlen++] = hexchar((unsigned char)src[i] / 16); + dst[dlen++] = hexchar((unsigned char)src[i] % 16); + } else { + dst[dlen++] = src[i]; + } + dst[dlen++] = 0; + + *dstp = dst; + return 1; +} + +int +escape(const char *src, unsigned int slen, char **dstp) +{ + return escape2(src, slen, dstp, PFALSE); +} + +int byteArrayToString(unsigned char *bytes, int length, char *string) +{ + int i; + for(i=0;i<length;i++) + { + sprintf(string+(i*2), "%02x", bytes[i]); + } + return EPHIDGET_OK; +} + +int stringToByteArray(char *string, unsigned char *bytes, int *length) +{ + int i; + + if(strlen(string) > (size_t)((*length)*2)) + return EPHIDGET_INVALIDARG; + + for(i=0;i<(int)strlen(string);i+=2) + { + if(hexval(string[i])==-1) + break; + if((i/2)>*length) + return EPHIDGET_INVALIDARG; + bytes[i/2] = (hexval(string[i])<<4)+hexval(string[i+1]); + } + *length = i/2; + + return EPHIDGET_OK; +} + +//up to 1048575 (0xFFFFF) per int (not full 32-bit!) +//IR max is 327670 +int wordArrayToString(int *words, int length, char *string) +{ + int i; + for(i=0;i<length;i++) + { + if(words[i] > 0xFFFFF) + sprintf(string+(i*5), "fffff"); + else + sprintf(string+(i*5), "%05x", words[i]); + } + return EPHIDGET_OK; +} + +//up to 1048575 (0xFFFFF) per int (not full 32-bit!) +int stringToWordArray(char *string, int *words, int *length) +{ + int i; + + for(i=0;i<(int)strlen(string);i+=5) + { + if(hexval(string[i])==-1) + break; + if((i/5)>*length) + return EPHIDGET_INVALIDARG; + words[i/5] = (hexval(string[i])<<16)+ + (hexval(string[i+1])<<12)+ + (hexval(string[i+2])<<8)+ + (hexval(string[i+3])<<4)+ + hexval(string[i+4]); + if(words[i/5] == 0xfffff) + words[i/5] = PUNK_INT; + } + *length = i/5; + + return EPHIDGET_OK; +} diff --git a/utils/utils.h b/utils/utils.h new file mode 100644 index 0000000..cbc6309 --- /dev/null +++ b/utils/utils.h @@ -0,0 +1,49 @@ +#ifndef _UTILS_H_ +#define _UTILS_H_ +#include <regex.h> +#include <stdio.h> +#include <stdarg.h> + +typedef enum { + PUL_ERR = 1, + PUL_CRIT, + PUL_WARN, + PUL_INFO, + PUL_DEBUG, + PUL_VERB +} pu_log_level_t; + +int pasprintf(char **ret, const char *fmt, ...); +int pvasprintf(char **ret, const char *fmt, va_list ap); + +int pd_getline(char *buf, unsigned int bufsize, int *bufcur, int *buflen, + int(*readfunc)(int, void *, unsigned int, char *errdesc, int errlen), + int(*closefunc)(int, char *errdesc, int errlen), int readfd, + char **line, char *errdesc, int errlen); +//int pd_getline_simple(int fd, char **line); + +int getmatchsub(const char *line, char **subp, const regmatch_t pmatch[], + int n); +int stream_server_accept(int port, void(*clfunc)(int fd, const char *addr, + int port), char *errdesc, int errlen); +int CCONV stream_server_connect(const char *dest, const char *svcname, + int *fdp, int *cancelSocket, char *errdesc, int errdesclen); + +int pu_write(int fd, const void *buf, unsigned int len, char *errdesc, + int edlen); +int pu_read(int fd, void *buf, unsigned int len, char *errdesc, int edlen); +int pu_close(int fd, char *errdesc, int edlen); +extern int logging_enabled; +void pu_log_stream(FILE *); +void pu_log(pu_log_level_t l, int s, const char *fmt, ...); +int escape(const char *src, unsigned int srclen, char **dstp); +int escape2(const char *src, unsigned int slen, char **dstp, int escbacks); +int unescape(const char *src, char **dstp, unsigned int *dstlenp); +int cancelConnect(int cancelSocket); + +int byteArrayToString(unsigned char *bytes, int length, char *string); +int stringToByteArray(char *string, unsigned char *bytes, int *length); +int wordArrayToString(int *words, int length, char *string); +int stringToWordArray(char *string, int *words, int *length); + +#endif |