--- /dev/null
+*~
+build/
+.DS_Store
+*.xcodeproj/*.mode*
+*.xcodeproj/*.pbxuser
+*.xcodeproj/*.perspectivev3
+
+# /Libc.xcodeproj/
+/Libc.xcodeproj/project.xcworkspace
+/Libc.xcodeproj/xcuserdata
+/Libc.xcodeproj/xcshareddata
stdlib/FreeBSD/reallocf.c freebsd lib/libc/stdlib/reallocf.c 3dc97c4341b6c5a0163c12badc7f50628cecf4e6
stdtime/FreeBSD/strptime.c freebsd lib/libc/stdtime/strptime.c 52d53d171566c2cd975d2db86a291e516d34d9fe
stdtime/FreeBSD/strptime.3 freebsd lib/libc/stdtime/strptime.3 52d53d171566c2cd975d2db86a291e516d34d9fe
+string/FreeBSD/bcmp.3 freebsd lib/libc/string/bcmp.3 408f4a1ab49f89368c80edb4485895658fc81598
string/FreeBSD/memcmp.3 freebsd lib/libc/string/memcmp.3 3eb0ea4663f0ae19c4983e80963a121463224508
string/FreeBSD/strcpy.3 freebsd lib/libc/string/strcpy.3 cfc3df2b8f708ce8494d9d556e3472a5c8c21b8a
string/FreeBSD/strpbrk.3 freebsd lib/libc/string/strpbrk.3 5b882020081a138285227631c46a406c08e17bc8
string/FreeBSD/strspn.3 freebsd lib/libc/string/strspn.3 5b882020081a138285227631c46a406c08e17bc8
string/FreeBSD/strstr.3 freebsd lib/libc/string/strstr.3 cfc3df2b8f708ce8494d9d556e3472a5c8c21b8a
+string/FreeBSD/timingsafe_bcmp.3 freebsd lib/libc/string/timingsafe_bcmp.3 408f4a1ab49f89368c80edb4485895658fc81598
+string/FreeBSD/timingsafe_bcmp.c freebsd lib/libc/string/timingsafe_bcmp.c 408f4a1ab49f89368c80edb4485895658fc81598
tests/netbsd_getcwd.c freebsd contrib/netbsd-tests/lib/libc/gen/t_getcwd.c 6f5b3c1fa3e9554a26cbf6401366ff8b0f0506fe
tests/netbsd_getenv_thread.c freebsd contrib/netbsd-tests/lib/libc/stdlib/t_getenv_thread.c 3f09b8d0af642c2aeb96a4d667cefb7fe3bce443
tests/netbsd_stat.c freebsd contrib/netbsd-tests/lib/libc/sys/t_stat.c 6f5b3c1fa3e9554a26cbf6401366ff8b0f0506fe
63D4061113DDF4340094DD56 /* strncat.c in Sources */ = {isa = PBXBuildFile; fileRef = 63D4060F13DDF4340094DD56 /* strncat.c */; };
63D4061313DDF6A30094DD56 /* strlcat.c in Sources */ = {isa = PBXBuildFile; fileRef = 63D4061213DDF6A20094DD56 /* strlcat.c */; };
63D4061413DDF6A30094DD56 /* strlcat.c in Sources */ = {isa = PBXBuildFile; fileRef = 63D4061213DDF6A20094DD56 /* strlcat.c */; };
+ 928BD1001D76072200EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1011D76072200EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1021D76072C00EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1031D76073300EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1041D76073400EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1051D76073400EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1061D76073500EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1071D76073600EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
+ 928BD1081D76073600EC01FC /* timingsafe_bcmp.c in Sources */ = {isa = PBXBuildFile; fileRef = 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */; };
92ABC7E91D375FC2000DF880 /* compatibility_hacks.c in Sources */ = {isa = PBXBuildFile; fileRef = 92ABC7E81D375FC2000DF880 /* compatibility_hacks.c */; };
B10BC41C14338AEB005E4366 /* regcomp.c in Sources */ = {isa = PBXBuildFile; fileRef = B122F2B11432B95B00AF95D0 /* regcomp.c */; settings = {COMPILER_FLAGS = "-DHAVE_CONFIG_H -I$(SRCROOT)/regex/TRE -I$(SRCROOT)/regex/FreeBSD"; }; };
B122F2C71432B95B00AF95D0 /* regcomp.c in Sources */ = {isa = PBXBuildFile; fileRef = B122F2B11432B95B00AF95D0 /* regcomp.c */; };
/* Begin PBXFileReference section */
147CDFCF1B7C14FA00831EC6 /* clock_gettime.3 */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = clock_gettime.3; sourceTree = "<group>"; };
147CDFD01B7C14FA00831EC6 /* clock_gettime.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = clock_gettime.c; sourceTree = "<group>"; };
- 2B9D61B6157D667000AF25B8 /* trace.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = trace.h; path = os/trace.h; sourceTree = "<group>"; };
2DF67CDD184F9CBE00B83A3D /* debug_private.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = debug_private.c; path = os/debug_private.c; sourceTree = "<group>"; };
2DF67CE7184F9CD000B83A3D /* debug_private.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = debug_private.h; path = os/debug_private.h; sourceTree = "<group>"; };
3F169A3C1643B7BA0029E851 /* memccpy_chk.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = memccpy_chk.c; sourceTree = "<group>"; };
63D4060C13DDF26A0094DD56 /* strcat.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = strcat.c; sourceTree = "<group>"; };
63D4060F13DDF4340094DD56 /* strncat.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = strncat.c; sourceTree = "<group>"; };
63D4061213DDF6A20094DD56 /* strlcat.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = strlcat.c; sourceTree = "<group>"; };
+ 928BD0FD1D7606EA00EC01FC /* timingsafe_bcmp.3 */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = timingsafe_bcmp.3; sourceTree = "<group>"; };
+ 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = timingsafe_bcmp.c; sourceTree = "<group>"; };
+ 928BD1091D7608A400EC01FC /* environ.7 */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = environ.7; sourceTree = "<group>"; };
92ABC7E81D375FC2000DF880 /* compatibility_hacks.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = compatibility_hacks.c; sourceTree = "<group>"; };
B122F2AD1432B8E600AF95D0 /* libTRE.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libTRE.a; sourceTree = BUILT_PRODUCTS_DIR; };
B122F2AF1432B95B00AF95D0 /* config.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = config.h; sourceTree = "<group>"; };
C9B539F8138D9E990028D27C /* xlocale_private.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = xlocale_private.h; sourceTree = "<group>"; };
C9B53A05138D9E990028D27C /* assert.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = assert.3; sourceTree = "<group>"; };
C9B53A06138D9E990028D27C /* bitstring.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = bitstring.3; sourceTree = "<group>"; };
- C9B53A07138D9E990028D27C /* environ.7 */ = {isa = PBXFileReference; lastKnownFileType = text; path = environ.7; sourceTree = "<group>"; };
C9B53A09138D9E990028D27C /* stdarg.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = stdarg.3; sourceTree = "<group>"; };
C9B53A0B138D9E990028D27C /* gethostuuid.2 */ = {isa = PBXFileReference; lastKnownFileType = text; path = gethostuuid.2; sourceTree = "<group>"; };
C9B53A0D138D9E990028D27C /* utmp.5 */ = {isa = PBXFileReference; lastKnownFileType = text; path = utmp.5; sourceTree = "<group>"; };
C9B53D24138D9E9A0028D27C /* strcoll.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = strcoll.3; sourceTree = "<group>"; };
C9B53D26138D9E9A0028D27C /* strcoll.c */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.c; path = strcoll.c; sourceTree = "<group>"; };
C9B53D28138D9E9A0028D27C /* strcpy.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = strcpy.3; sourceTree = "<group>"; };
- C9B53D2B138D9E9A0028D27C /* strcspn.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = strcspn.3; sourceTree = "<group>"; };
C9B53D2D138D9E9A0028D27C /* strcspn.c */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.c; path = strcspn.c; sourceTree = "<group>"; };
C9B53D2E138D9E9A0028D27C /* strdup.3 */ = {isa = PBXFileReference; lastKnownFileType = text; path = strdup.3; sourceTree = "<group>"; };
C9B53D30138D9E9A0028D27C /* strdup.c */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.c; path = strdup.c; sourceTree = "<group>"; };
children = (
2DF67CE7184F9CD000B83A3D /* debug_private.h */,
2DF67CDD184F9CBE00B83A3D /* debug_private.c */,
- 2B9D61B6157D667000AF25B8 /* trace.h */,
4B2C64AB15519C3400342BFA /* assumes.h */,
4B2C64A215519BAF00342BFA /* assumes.c */,
);
children = (
C9B53A05138D9E990028D27C /* assert.3 */,
C9B53A06138D9E990028D27C /* bitstring.3 */,
- C9B53A07138D9E990028D27C /* environ.7 */,
C9B53A08138D9E990028D27C /* FreeBSD */,
C9B53A0B138D9E990028D27C /* gethostuuid.2 */,
C9B53A0D138D9E990028D27C /* utmp.5 */,
C9B53A08138D9E990028D27C /* FreeBSD */ = {
isa = PBXGroup;
children = (
+ 928BD1091D7608A400EC01FC /* environ.7 */,
C9B53A09138D9E990028D27C /* stdarg.3 */,
);
path = FreeBSD;
C9B53D24138D9E9A0028D27C /* strcoll.3 */,
C9B53D26138D9E9A0028D27C /* strcoll.c */,
C9B53D28138D9E9A0028D27C /* strcpy.3 */,
- C9B53D2B138D9E9A0028D27C /* strcspn.3 */,
C9B53D2D138D9E9A0028D27C /* strcspn.c */,
C9B53D2E138D9E9A0028D27C /* strdup.3 */,
C9B53D30138D9E9A0028D27C /* strdup.c */,
C9B53D5D138D9E9A0028D27C /* strxfrm.c */,
C9B53D5F138D9E9A0028D27C /* swab.3 */,
C9B53D61138D9E9A0028D27C /* swab.c */,
+ 928BD0FD1D7606EA00EC01FC /* timingsafe_bcmp.3 */,
+ 928BD0FE1D7606EA00EC01FC /* timingsafe_bcmp.c */,
C9B53D63138D9E9A0028D27C /* wcpcpy.c */,
C9B53D64138D9E9A0028D27C /* wcpncpy.c */,
C9B53D65138D9E9A0028D27C /* wcscasecmp.c */,
C0E343931C582ECB00E749C2 /* strcpy.s in Sources */,
C0E343941C582ECB00E749C2 /* strlcat.s in Sources */,
C0E343951C582ECB00E749C2 /* strlcpy.s in Sources */,
+ 928BD1011D76072200EC01FC /* timingsafe_bcmp.c in Sources */,
C0E343961C582ECB00E749C2 /* strlen.s in Sources */,
C0E343971C582ECB00E749C2 /* strncpy.s in Sources */,
C0E343981C582ECB00E749C2 /* strlen.s in Sources */,
C9257EF8138E1C5D00B3107C /* rec_search.c in Sources */,
C9257EF9138E1C5D00B3107C /* rec_seq.c in Sources */,
C9257EFA138E1C5D00B3107C /* rec_utils.c in Sources */,
+ 928BD1021D76072C00EC01FC /* timingsafe_bcmp.c in Sources */,
C9257EFB138E1C6A00B3107C /* _hdtoa.c in Sources */,
C9257EFC138E1C6A00B3107C /* gdtoa-dmisc.c in Sources */,
C9257EFD138E1C6A00B3107C /* gdtoa-dtoa.c in Sources */,
C94211CA13900C8A004BA536 /* getchar.c in Sources */,
C94211CB13900C8A004BA536 /* getdelim.c in Sources */,
C94211CC13900C8A004BA536 /* getline.c in Sources */,
+ 928BD1001D76072200EC01FC /* timingsafe_bcmp.c in Sources */,
C94211CD13900C8A004BA536 /* gets.c in Sources */,
C94211CE13900C8A004BA536 /* getw.c in Sources */,
C94211CF13900C8A004BA536 /* getwc.c in Sources */,
C95B8075138F3C55004311DA /* getchar.c in Sources */,
C95B8076138F3C55004311DA /* getdelim.c in Sources */,
C95B8077138F3C55004311DA /* getline.c in Sources */,
+ 928BD1041D76073400EC01FC /* timingsafe_bcmp.c in Sources */,
C95B8078138F3C55004311DA /* gets.c in Sources */,
C95B8079138F3C55004311DA /* getw.c in Sources */,
C95B807A138F3C55004311DA /* getwc.c in Sources */,
C95B8320138F52B0004311DA /* getchar.c in Sources */,
C95B8321138F52B0004311DA /* getdelim.c in Sources */,
C95B8322138F52B0004311DA /* getline.c in Sources */,
+ 928BD1051D76073400EC01FC /* timingsafe_bcmp.c in Sources */,
C95B8323138F52B0004311DA /* gets.c in Sources */,
C95B8324138F52B0004311DA /* getw.c in Sources */,
C95B8325138F52B0004311DA /* getwc.c in Sources */,
C95B85C6138F53DB004311DA /* getchar.c in Sources */,
C95B85C7138F53DB004311DA /* getdelim.c in Sources */,
C95B85C8138F53DB004311DA /* getline.c in Sources */,
+ 928BD1061D76073500EC01FC /* timingsafe_bcmp.c in Sources */,
C95B85C9138F53DB004311DA /* gets.c in Sources */,
C95B85CA138F53DB004311DA /* getw.c in Sources */,
C95B85CB138F53DB004311DA /* getwc.c in Sources */,
C976604A138EC61A00741512 /* getchar.c in Sources */,
C976604B138EC61A00741512 /* getdelim.c in Sources */,
C976604C138EC61A00741512 /* getline.c in Sources */,
+ 928BD1031D76073300EC01FC /* timingsafe_bcmp.c in Sources */,
C976604D138EC61A00741512 /* gets.c in Sources */,
C976604E138EC61A00741512 /* getw.c in Sources */,
C976604F138EC61A00741512 /* getwc.c in Sources */,
C9EB3090138F6D880075BB52 /* nftw.c in Sources */,
C9EB3091138F6D880075BB52 /* nlist.c in Sources */,
C9EB3093138F6D880075BB52 /* oldsyslog.c in Sources */,
+ 928BD1071D76073600EC01FC /* timingsafe_bcmp.c in Sources */,
C9EB3096138F6D880075BB52 /* setlogin.c in Sources */,
C9EB3097138F6D880075BB52 /* sigsetops.c in Sources */,
C9EB309A138F6D880075BB52 /* strtofflags.c in Sources */,
C9EB3337138F75580075BB52 /* nftw.c in Sources */,
C9EB3338138F75580075BB52 /* nlist.c in Sources */,
C9EB333A138F75580075BB52 /* oldsyslog.c in Sources */,
+ 928BD1081D76073600EC01FC /* timingsafe_bcmp.c in Sources */,
C9EB333D138F75580075BB52 /* setlogin.c in Sources */,
C9EB333E138F75580075BB52 /* sigsetops.c in Sources */,
C9EB3341138F75580075BB52 /* strtofflags.c in Sources */,
#if TARGET_OS_IPHONE
/* <rdar://problem/13875458> */
+#if defined(__OPEN_SOURCE__) || !__LP64__
#include <wordexp.h>
int wordexp(const char *restrict words __unused, wordexp_t *restrict pwordexp __unused, int flags __unused) {
return WRDE_NOSPACE;
void wordfree(wordexp_t *pwordexp __unused) {
}
+#else
+struct __not_an_empty_c_file;
+#endif
#else
/* SUS places swab() in unistd.h. It is listed here for source compatibility */
void swab(const void * __restrict, void * __restrict, ssize_t);
+
+#ifndef __CUDACC__
+__OSX_AVAILABLE(10.12.1) __IOS_AVAILABLE(10.1)
+__TVOS_AVAILABLE(10.0.1) __WATCHOS_AVAILABLE(3.1)
+#endif
+int timingsafe_bcmp(const void *__b1, const void *__b2, size_t __len);
__END_DECLS
/* Some functions historically defined in string.h were placed in strings.h
timegm.3 timegm.3 timelocal.3
times.3 times.3
timezone.3 timezone.3
+timingsafe_bcmp.3 timingsafe_bcmp.3
tmpnam.3 tmpnam.3 tempnam.3 tmpfile.3
toascii.3 toascii.3
tolower.3 tolower.3 tolower_l.3
+++ /dev/null
-.
\ No newline at end of file
--- /dev/null
+/****************************************************************************/
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
+#endif /* LIBC_SCCS and not lint */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $");
+
+#include <stdlib.h>
+#include <pthread.h>
+#include <dispatch/dispatch.h>
+#include <stddef.h>
+#include <string.h>
+#include <libkern/OSAtomic.h>
+#include <sys/mman.h>
+#include <errno.h>
+#define __APPLE_API_PRIVATE
+#include <machine/cpu_capabilities.h>
+
+#ifdef I_AM_PSORT_R
+typedef int cmp_t(void *, const void *, const void *);
+#else
+typedef int cmp_t(const void *, const void *);
+#endif
+#ifdef I_AM_PSORT_B
+static inline char *med3(char *, char *, char *, cmp_t ^, void *) __attribute__((always_inline));
+#else
+static inline char *med3(char *, char *, char *, cmp_t *, void *) __attribute__((always_inline));
+#endif
+static inline void swapfunc(char *, char *, int, int) __attribute__((always_inline));
+
+#define min(a, b) (a) < (b) ? a : b
+
+#define NARGS ((PAGESIZE - offsetof(struct page, args)) / sizeof(union args))
+#define PAGESIZE 4096
+#define PARALLEL_MIN_SIZE 2000 /* determine heuristically */
+
+struct shared; /* forward reference */
+union args {
+ union args *next;
+ struct {
+ struct shared *shared;
+ void *a;
+ size_t n;
+ int depth_limit;
+ } /* anonymous */;
+};
+
+struct page {
+ struct page *next;
+ union args args[0];
+};
+
+struct shared {
+ char *who;
+ union args *freelist;
+ struct page *pagelist;
+#ifdef I_AM_PSORT_R
+ void *thunk;
+#endif
+#ifdef I_AM_PSORT_B
+ cmp_t ^cmp;
+#else
+ cmp_t *cmp;
+#endif
+ size_t es;
+ size_t turnoff;
+ dispatch_queue_t queue;
+ dispatch_group_t group;
+ OSSpinLock sharedlock;
+};
+
+static union args *
+getargs(struct shared *shared)
+{
+ union args *args;
+
+ OSSpinLockLock(&shared->sharedlock);
+ if(!shared->freelist) {
+ struct page *page;
+ union args *prev;
+ int i;
+ if((page = (struct page *)mmap(NULL, PAGESIZE, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0)) == NULL)
+ return NULL;
+ page->next = shared->pagelist;
+ shared->pagelist = page;
+ prev = NULL;
+ for(args = page->args, i = NARGS; i > 0; args++, i--) {
+ args->next = prev;
+ prev = args;
+ }
+ shared->freelist = prev;
+ }
+ args = shared->freelist;
+ shared->freelist = args->next;
+ OSSpinLockUnlock(&shared->sharedlock);
+ return args;
+}
+
+static void
+returnargs(struct shared *shared, union args *args)
+{
+ OSSpinLockLock(&shared->sharedlock);
+ args->next = shared->freelist;
+ shared->freelist = args;
+ OSSpinLockUnlock(&shared->sharedlock);
+}
+
+/*
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ */
+#define swapcode(TYPE, parmi, parmj, n) { \
+ long i = (n) / sizeof (TYPE); \
+ TYPE *pi = (TYPE *) (parmi); \
+ TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+}
+
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static inline void
+swapfunc(a, b, n, swaptype)
+ char *a, *b;
+ int n, swaptype;
+{
+ if(swaptype <= 1)
+ swapcode(long, a, b, n)
+ else
+ swapcode(char, a, b, n)
+}
+
+#define swap(a, b) \
+ if (swaptype == 0) { \
+ long t = *(long *)(a); \
+ *(long *)(a) = *(long *)(b); \
+ *(long *)(b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype)
+
+#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
+
+#ifdef I_AM_PSORT_R
+#define CMP(t, x, y) (cmp((t), (x), (y)))
+#else
+#define CMP(t, x, y) (cmp((x), (y)))
+#endif
+
+static inline char *
+med3(char *a, char *b, char *c,
+#ifdef I_AM_PSORT_B
+cmp_t ^cmp,
+#else
+cmp_t *cmp,
+#endif
+void *thunk
+#ifndef I_AM_PSORT_R
+__unused
+#endif
+)
+{
+ return CMP(thunk, a, b) < 0 ?
+ (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
+ :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
+}
+
+#ifdef __LP64__
+#define DEPTH(x) (2 * (flsl((long)(x)) - 1))
+#else /* !__LP64__ */
+#define DEPTH(x) (2 * (fls((int)(x)) - 1))
+#endif /* __LP64__ */
+
+#ifdef I_AM_PSORT_R
+int __heapsort_r(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *));
+#endif
+
+static void _psort_parallel(void *x);
+
+static void
+_psort(void *a, size_t n, size_t es,
+#ifdef I_AM_PSORT_R
+void *thunk,
+#else
+#define thunk NULL
+#endif
+#ifdef I_AM_PSORT_B
+cmp_t ^cmp,
+#else
+cmp_t *cmp,
+#endif
+int depth_limit, struct shared *shared)
+{
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ size_t d, r;
+ int cmp_result;
+ int swaptype, swap_cnt;
+
+loop:
+ if (depth_limit-- <= 0) {
+#ifdef I_AM_PSORT_B
+ heapsort_b(a, n, es, cmp);
+#elif defined(I_AM_PSORT_R)
+ __heapsort_r(a, n, es, thunk, cmp);
+#else
+ heapsort(a, n, es, cmp);
+#endif
+ return;
+ }
+ SWAPINIT(a, es);
+ swap_cnt = 0;
+ if (n < 7) {
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+ pm = (char *)a + (n / 2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = (char *)a + (n - 1) * es;
+ if (n > 40) {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
+ pm = med3(pm - d, pm, pm + d, cmp, thunk);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
+ }
+ pm = med3(pl, pm, pn, cmp, thunk);
+ }
+ swap(a, pm);
+ pa = pb = (char *)a + es;
+
+ pc = pd = (char *)a + (n - 1) * es;
+ for (;;) {
+ while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
+ if (cmp_result == 0) {
+ swap_cnt = 1;
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
+ if (cmp_result == 0) {
+ swap_cnt = 1;
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ swap_cnt = 1;
+ pb += es;
+ pc -= es;
+ }
+
+ pn = (char *)a + n * es;
+ r = min(pa - (char *)a, pb - pa);
+ vecswap(a, pb - r, r);
+ r = min(pd - pc, pn - pd - es);
+ vecswap(pb, pn - r, r);
+
+ if (swap_cnt == 0) { /* Switch to insertion sort */
+ r = 1 + n / 4; /* n >= 7, so r >= 2 */
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+ pl -= es) {
+ swap(pl, pl - es);
+ if (++swap_cnt > r) goto nevermind;
+ }
+ return;
+ }
+
+nevermind:
+ if ((r = pb - pa) > es) {
+ r /= es;
+ if (shared && r > shared->turnoff) {
+ union args *args = getargs(shared);
+
+ if (args == NULL)
+ LIBC_ABORT("%s: getargs: %s", shared->who, strerror(errno));
+ args->shared = shared;
+ args->a = a;
+ args->n = r;
+ args->depth_limit = depth_limit;
+ dispatch_group_async_f(shared->group, shared->queue, args,
+ _psort_parallel);
+ } else {
+#ifdef I_AM_PSORT_R
+ _psort(a, r, es, thunk, cmp, depth_limit, NULL);
+#else
+ _psort(a, r, es, cmp, depth_limit, NULL);
+#endif
+ }
+ }
+ if ((r = pd - pc) > es) {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
+/* psort(pn - r, r / es, es, cmp);*/
+}
+
+static void
+_psort_parallel(void *x)
+{
+ union args *args = (union args *)x;
+ struct shared *shared = args->shared;
+
+ _psort(args->a, args->n, shared->es,
+#ifdef I_AM_PSORT_R
+ shared->thunk,
+#endif
+ shared->cmp, args->depth_limit, shared);
+ returnargs(shared, args);
+}
+
+/* fast, approximate integer square root */
+static size_t
+isqrt(size_t x)
+{
+ size_t s = 1L << (flsl(x) / 2);
+ return (s + x / s) / 2;
+}
+
+void
+#ifdef I_AM_PSORT_R
+psort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
+#elif defined(I_AM_PSORT_B)
+psort_b(void *a, size_t n, size_t es, cmp_t ^cmp)
+#else
+psort(void *a, size_t n, size_t es, cmp_t *cmp)
+#endif
+{
+ if (n >= PARALLEL_MIN_SIZE && _NumCPUs() > 1) {
+ struct shared shared;
+ union args *args;
+
+ bzero(&shared, sizeof(shared));
+ shared.sharedlock = OS_SPINLOCK_INIT;
+ if ((args = getargs(&shared)) != NULL) {
+ struct page *p, *pp;
+#ifdef I_AM_PSORT_R
+ shared.who = "psort_r";
+ shared.thunk = thunk;
+#elif defined(I_AM_PSORT_B)
+ shared.who = "psort_b";
+#else
+ shared.who = "psort";
+#endif
+ shared.cmp = cmp;
+ shared.es = es;
+ shared.queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+ shared.group = dispatch_group_create();
+ args->a = a;
+ args->n = n;
+ args->depth_limit = DEPTH(n);
+ args->shared = &shared;
+ /*
+ * The turnoff value is the size of a partition that,
+ * below which, we stop doing in parallel, and just do
+ * in the current thread. The value of sqrt(n) was
+ * determined heuristically. There is a smaller
+ * dependence on the slowness of the comparison
+ * function, and there might be a dependence on the
+ * number of processors, but the algorithm has not been
+ * determined. Because the sensitivity to the turnoff
+ * value is relatively low, we use a fast, approximate
+ * integer square root routine that is good enough for
+ * this purpose.
+ */
+ shared.turnoff = isqrt(n);
+ _psort_parallel(args);
+
+ /* wait for queue to drain */
+ dispatch_group_wait(shared.group, DISPATCH_TIME_FOREVER);
+ dispatch_release(shared.group);
+ for(p = shared.pagelist; p; p = pp) {
+ pp = p->next;
+ munmap(p, PAGESIZE);
+ }
+ return;
+ }
+ }
+ /* Just call qsort */
+#ifdef I_AM_PSORT_R
+ qsort_r(a, n, es, thunk, cmp);
+#elif defined(I_AM_PSORT_B)
+ qsort_b(a, n, es, cmp);
+#else
+ qsort(a, n, es, cmp);
+#endif
+}
+++ /dev/null
-.
\ No newline at end of file
--- /dev/null
+/****************************************************************************/
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
+#endif /* LIBC_SCCS and not lint */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $");
+
+#include <stdlib.h>
+#include <pthread.h>
+#include <dispatch/dispatch.h>
+#include <stddef.h>
+#include <string.h>
+#include <libkern/OSAtomic.h>
+#include <sys/mman.h>
+#include <errno.h>
+#define __APPLE_API_PRIVATE
+#include <machine/cpu_capabilities.h>
+
+#ifdef I_AM_PSORT_R
+typedef int cmp_t(void *, const void *, const void *);
+#else
+typedef int cmp_t(const void *, const void *);
+#endif
+#ifdef I_AM_PSORT_B
+static inline char *med3(char *, char *, char *, cmp_t ^, void *) __attribute__((always_inline));
+#else
+static inline char *med3(char *, char *, char *, cmp_t *, void *) __attribute__((always_inline));
+#endif
+static inline void swapfunc(char *, char *, int, int) __attribute__((always_inline));
+
+#define min(a, b) (a) < (b) ? a : b
+
+#define NARGS ((PAGESIZE - offsetof(struct page, args)) / sizeof(union args))
+#define PAGESIZE 4096
+#define PARALLEL_MIN_SIZE 2000 /* determine heuristically */
+
+struct shared; /* forward reference */
+union args {
+ union args *next;
+ struct {
+ struct shared *shared;
+ void *a;
+ size_t n;
+ int depth_limit;
+ } /* anonymous */;
+};
+
+struct page {
+ struct page *next;
+ union args args[0];
+};
+
+struct shared {
+ char *who;
+ union args *freelist;
+ struct page *pagelist;
+#ifdef I_AM_PSORT_R
+ void *thunk;
+#endif
+#ifdef I_AM_PSORT_B
+ cmp_t ^cmp;
+#else
+ cmp_t *cmp;
+#endif
+ size_t es;
+ size_t turnoff;
+ dispatch_queue_t queue;
+ dispatch_group_t group;
+ OSSpinLock sharedlock;
+};
+
+static union args *
+getargs(struct shared *shared)
+{
+ union args *args;
+
+ OSSpinLockLock(&shared->sharedlock);
+ if(!shared->freelist) {
+ struct page *page;
+ union args *prev;
+ int i;
+ if((page = (struct page *)mmap(NULL, PAGESIZE, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0)) == NULL)
+ return NULL;
+ page->next = shared->pagelist;
+ shared->pagelist = page;
+ prev = NULL;
+ for(args = page->args, i = NARGS; i > 0; args++, i--) {
+ args->next = prev;
+ prev = args;
+ }
+ shared->freelist = prev;
+ }
+ args = shared->freelist;
+ shared->freelist = args->next;
+ OSSpinLockUnlock(&shared->sharedlock);
+ return args;
+}
+
+static void
+returnargs(struct shared *shared, union args *args)
+{
+ OSSpinLockLock(&shared->sharedlock);
+ args->next = shared->freelist;
+ shared->freelist = args;
+ OSSpinLockUnlock(&shared->sharedlock);
+}
+
+/*
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ */
+#define swapcode(TYPE, parmi, parmj, n) { \
+ long i = (n) / sizeof (TYPE); \
+ TYPE *pi = (TYPE *) (parmi); \
+ TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+}
+
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static inline void
+swapfunc(a, b, n, swaptype)
+ char *a, *b;
+ int n, swaptype;
+{
+ if(swaptype <= 1)
+ swapcode(long, a, b, n)
+ else
+ swapcode(char, a, b, n)
+}
+
+#define swap(a, b) \
+ if (swaptype == 0) { \
+ long t = *(long *)(a); \
+ *(long *)(a) = *(long *)(b); \
+ *(long *)(b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype)
+
+#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
+
+#ifdef I_AM_PSORT_R
+#define CMP(t, x, y) (cmp((t), (x), (y)))
+#else
+#define CMP(t, x, y) (cmp((x), (y)))
+#endif
+
+static inline char *
+med3(char *a, char *b, char *c,
+#ifdef I_AM_PSORT_B
+cmp_t ^cmp,
+#else
+cmp_t *cmp,
+#endif
+void *thunk
+#ifndef I_AM_PSORT_R
+__unused
+#endif
+)
+{
+ return CMP(thunk, a, b) < 0 ?
+ (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
+ :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
+}
+
+#ifdef __LP64__
+#define DEPTH(x) (2 * (flsl((long)(x)) - 1))
+#else /* !__LP64__ */
+#define DEPTH(x) (2 * (fls((int)(x)) - 1))
+#endif /* __LP64__ */
+
+#ifdef I_AM_PSORT_R
+int __heapsort_r(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *));
+#endif
+
+static void _psort_parallel(void *x);
+
+static void
+_psort(void *a, size_t n, size_t es,
+#ifdef I_AM_PSORT_R
+void *thunk,
+#else
+#define thunk NULL
+#endif
+#ifdef I_AM_PSORT_B
+cmp_t ^cmp,
+#else
+cmp_t *cmp,
+#endif
+int depth_limit, struct shared *shared)
+{
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ size_t d, r;
+ int cmp_result;
+ int swaptype, swap_cnt;
+
+loop:
+ if (depth_limit-- <= 0) {
+#ifdef I_AM_PSORT_B
+ heapsort_b(a, n, es, cmp);
+#elif defined(I_AM_PSORT_R)
+ __heapsort_r(a, n, es, thunk, cmp);
+#else
+ heapsort(a, n, es, cmp);
+#endif
+ return;
+ }
+ SWAPINIT(a, es);
+ swap_cnt = 0;
+ if (n < 7) {
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+ pm = (char *)a + (n / 2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = (char *)a + (n - 1) * es;
+ if (n > 40) {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
+ pm = med3(pm - d, pm, pm + d, cmp, thunk);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
+ }
+ pm = med3(pl, pm, pn, cmp, thunk);
+ }
+ swap(a, pm);
+ pa = pb = (char *)a + es;
+
+ pc = pd = (char *)a + (n - 1) * es;
+ for (;;) {
+ while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
+ if (cmp_result == 0) {
+ swap_cnt = 1;
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
+ if (cmp_result == 0) {
+ swap_cnt = 1;
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ swap_cnt = 1;
+ pb += es;
+ pc -= es;
+ }
+
+ pn = (char *)a + n * es;
+ r = min(pa - (char *)a, pb - pa);
+ vecswap(a, pb - r, r);
+ r = min(pd - pc, pn - pd - es);
+ vecswap(pb, pn - r, r);
+
+ if (swap_cnt == 0) { /* Switch to insertion sort */
+ r = 1 + n / 4; /* n >= 7, so r >= 2 */
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm;
+ pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
+ pl -= es) {
+ swap(pl, pl - es);
+ if (++swap_cnt > r) goto nevermind;
+ }
+ return;
+ }
+
+nevermind:
+ if ((r = pb - pa) > es) {
+ r /= es;
+ if (shared && r > shared->turnoff) {
+ union args *args = getargs(shared);
+
+ if (args == NULL)
+ LIBC_ABORT("%s: getargs: %s", shared->who, strerror(errno));
+ args->shared = shared;
+ args->a = a;
+ args->n = r;
+ args->depth_limit = depth_limit;
+ dispatch_group_async_f(shared->group, shared->queue, args,
+ _psort_parallel);
+ } else {
+#ifdef I_AM_PSORT_R
+ _psort(a, r, es, thunk, cmp, depth_limit, NULL);
+#else
+ _psort(a, r, es, cmp, depth_limit, NULL);
+#endif
+ }
+ }
+ if ((r = pd - pc) > es) {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
+/* psort(pn - r, r / es, es, cmp);*/
+}
+
+static void
+_psort_parallel(void *x)
+{
+ union args *args = (union args *)x;
+ struct shared *shared = args->shared;
+
+ _psort(args->a, args->n, shared->es,
+#ifdef I_AM_PSORT_R
+ shared->thunk,
+#endif
+ shared->cmp, args->depth_limit, shared);
+ returnargs(shared, args);
+}
+
+/* fast, approximate integer square root */
+static size_t
+isqrt(size_t x)
+{
+ size_t s = 1L << (flsl(x) / 2);
+ return (s + x / s) / 2;
+}
+
+void
+#ifdef I_AM_PSORT_R
+psort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
+#elif defined(I_AM_PSORT_B)
+psort_b(void *a, size_t n, size_t es, cmp_t ^cmp)
+#else
+psort(void *a, size_t n, size_t es, cmp_t *cmp)
+#endif
+{
+ if (n >= PARALLEL_MIN_SIZE && _NumCPUs() > 1) {
+ struct shared shared;
+ union args *args;
+
+ bzero(&shared, sizeof(shared));
+ shared.sharedlock = OS_SPINLOCK_INIT;
+ if ((args = getargs(&shared)) != NULL) {
+ struct page *p, *pp;
+#ifdef I_AM_PSORT_R
+ shared.who = "psort_r";
+ shared.thunk = thunk;
+#elif defined(I_AM_PSORT_B)
+ shared.who = "psort_b";
+#else
+ shared.who = "psort";
+#endif
+ shared.cmp = cmp;
+ shared.es = es;
+ shared.queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+ shared.group = dispatch_group_create();
+ args->a = a;
+ args->n = n;
+ args->depth_limit = DEPTH(n);
+ args->shared = &shared;
+ /*
+ * The turnoff value is the size of a partition that,
+ * below which, we stop doing in parallel, and just do
+ * in the current thread. The value of sqrt(n) was
+ * determined heuristically. There is a smaller
+ * dependence on the slowness of the comparison
+ * function, and there might be a dependence on the
+ * number of processors, but the algorithm has not been
+ * determined. Because the sensitivity to the turnoff
+ * value is relatively low, we use a fast, approximate
+ * integer square root routine that is good enough for
+ * this purpose.
+ */
+ shared.turnoff = isqrt(n);
+ _psort_parallel(args);
+
+ /* wait for queue to drain */
+ dispatch_group_wait(shared.group, DISPATCH_TIME_FOREVER);
+ dispatch_release(shared.group);
+ for(p = shared.pagelist; p; p = pp) {
+ pp = p->next;
+ munmap(p, PAGESIZE);
+ }
+ return;
+ }
+ }
+ /* Just call qsort */
+#ifdef I_AM_PSORT_R
+ qsort_r(a, n, es, thunk, cmp);
+#elif defined(I_AM_PSORT_B)
+ qsort_b(a, n, es, cmp);
+#else
+ qsort(a, n, es, cmp);
+#endif
+}
.\" 2. Redistributions in binary form must reproduce the above copyright
.\" notice, this list of conditions and the following disclaimer in the
.\" documentation and/or other materials provided with the distribution.
-.\" 4. Neither the name of the University nor the names of its contributors
+.\" 3. Neither the name of the University nor the names of its contributors
.\" may be used to endorse or promote products derived from this software
.\" without specific prior written permission.
.\"
.\" SUCH DAMAGE.
.\"
.\" @(#)bcmp.3 8.1 (Berkeley) 6/4/93
-.\" $FreeBSD: src/lib/libc/string/bcmp.3,v 1.11 2007/01/09 00:28:11 imp Exp $
+.\" $FreeBSD$
.\"
-.Dd June 4, 1993
+.Dd August 15, 2016
.Dt BCMP 3
.Os
.Sh NAME
.Sh SYNOPSIS
.In strings.h
.Ft int
-.Fn bcmp "const void *s1" "const void *s2" "size_t n"
+.Fn bcmp "const void *b1" "const void *b2" "size_t len"
.Sh DESCRIPTION
The
.Fn bcmp
function
compares byte string
-.Fa s1
+.Fa b1
against byte string
-.Fa s2 ,
+.Fa b2 ,
returning zero if they are identical, non-zero otherwise.
Both strings are assumed to be
-.Fa n
+.Fa len
bytes long.
Zero-length strings are always identical.
.Pp
.Xr strcasecmp 3 ,
.Xr strcmp 3 ,
.Xr strcoll 3 ,
-.Xr strxfrm 3
+.Xr strxfrm 3 ,
+.Xr timingsafe_bcmp 3
.Sh HISTORY
A
.Fn bcmp
--- /dev/null
+.\" $OpenBSD: timingsafe_bcmp.3,v 1.2 2014/06/21 20:22:15 tedu Exp $
+.\"
+.\" Copyright (c) 2014 Google Inc.
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.\" $FreeBSD$
+.Dd August 15, 2016
+.Dt TIMINGSAFE_BCMP 3
+.Os
+.Sh NAME
+.Nm timingsafe_bcmp
+.Nd timing-safe byte sequence comparisons
+.Sh SYNOPSIS
+.In string.h
+.Ft int
+.Fn timingsafe_bcmp "const void *b1" "const void *b2" "size_t len"
+.Sh DESCRIPTION
+The
+.Fn timingsafe_bcmp
+function compares the first
+.Fa len
+bytes pointed to by
+.Fa b1
+and
+.Fa b2 .
+.Pp
+Additionally, the running time is independent of the byte sequences compared,
+making it safe to use for comparing secret values such as cryptographic MACs.
+In contrast,
+.Xr bcmp 3
+and
+.Xr memcmp 3
+may short-circuit after finding the first differing byte.
+.Sh RETURN VALUES
+The
+.Fn timingsafe_bcmp
+function returns 0 or not zero if the byte sequence pointed to by
+.Fa b1
+compares equal to or not equal to (respectively)
+the byte sequence pointed to by
+.Fa b2 .
+.Sh SEE ALSO
+.Xr bcmp 3
+.Sh STANDARDS
+The
+.Fn timingsafe_bcmp
+function is a non-standard extension.
+.Sh HISTORY
+The
+.Fn timingsafe_bcmp
+function first appeared in
+.Ox 4.9 ,
+.Fx 12.0 ,
+and macOS 10.12.1.
--- /dev/null
+/* $OpenBSD: timingsafe_bcmp.c,v 1.3 2015/08/31 02:53:57 guenther Exp $ */
+/*
+ * Copyright (c) 2010 Damien Miller. All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <string.h>
+
+int
+timingsafe_bcmp(const void *b1, const void *b2, size_t n)
+{
+ const unsigned char *p1 = b1, *p2 = b2;
+ int ret = 0;
+
+ for (; n > 0; n--)
+ ret |= *p1++ ^ *p2++;
+ return ret;
+}
--- /dev/null
+#include <string.h>
+#include <stdlib.h>
+
+#include <darwintest.h>
+
+T_DECL(timingsafe_bcmp, "tests for timingsafe_bcmp(3)")
+{
+ // empty
+ T_ASSERT_EQ(0, timingsafe_bcmp(NULL, NULL, 0), NULL);
+ T_ASSERT_EQ(0, timingsafe_bcmp("foo", "foo", 0), NULL);
+ T_ASSERT_EQ(0, timingsafe_bcmp("foo", "bar", 0), NULL);
+
+ // equal
+ T_ASSERT_EQ(0, timingsafe_bcmp("foo", "foo", strlen("foo")), NULL);
+
+ // unequal
+ T_ASSERT_NE(0, timingsafe_bcmp("foo", "bar", strlen("foo")), NULL);
+ T_ASSERT_NE(0, timingsafe_bcmp("foo", "goo", strlen("foo")), NULL);
+ T_ASSERT_NE(0, timingsafe_bcmp("foo", "fpo", strlen("foo")), NULL);
+ T_ASSERT_NE(0, timingsafe_bcmp("foo", "fop", strlen("foo")), NULL);
+
+ // large
+ char buf[1024 * 16];
+ arc4random_buf(buf, sizeof(buf));
+ T_ASSERT_EQ(0, timingsafe_bcmp(buf, buf, sizeof(buf)), NULL);
+ T_ASSERT_NE(0, timingsafe_bcmp(buf, buf + 1, sizeof(buf) - 1), NULL);
+ T_ASSERT_NE(0, timingsafe_bcmp(buf, buf + 128, 128), NULL);
+
+ memcpy(buf+128, buf, 128);
+ T_ASSERT_EQ(0, timingsafe_bcmp(buf, buf + 128, 128), NULL);
+}
projects / apple / libc.git / commitdiff
