diff options
Diffstat (limited to 'contrib')
54 files changed, 3608 insertions, 73 deletions
diff --git a/contrib/binutils/bfd/ppcboot.c b/contrib/binutils/bfd/ppcboot.c index da8c6b8019bd..54a482dc9ee3 100644 --- a/contrib/binutils/bfd/ppcboot.c +++ b/contrib/binutils/bfd/ppcboot.c @@ -419,7 +419,7 @@ ppcboot_bfd_print_private_bfd_data (abfd, farg) if (tdata->header.os_id) fprintf (f, "OS_ID = 0x%.2x\n", tdata->header.os_id); - if (tdata->header.partition_name) + if (tdata->header.partition_name[0]) fprintf (f, _("Partition name = \"%s\"\n"), tdata->header.partition_name); for (i = 0; i < 4; i++) diff --git a/contrib/blacklist/lib/bl.c b/contrib/blacklist/lib/bl.c index bca52cfbc8fe..3c3201d26aec 100644 --- a/contrib/blacklist/lib/bl.c +++ b/contrib/blacklist/lib/bl.c @@ -152,8 +152,8 @@ bl_init(bl_t b, bool srv) b->b_fd = socket(PF_LOCAL, SOCK_DGRAM|SOCK_CLOEXEC|SOCK_NONBLOCK|SOCK_NOSIGPIPE, 0); if (b->b_fd == -1) { - bl_log(b->b_fun, LOG_ERR, "%s: socket failed (%m)", - __func__); + bl_log(b->b_fun, LOG_ERR, "%s: socket failed (%s)", + __func__, strerror(errno)); BL_UNLOCK(b); return -1; } @@ -200,8 +200,8 @@ bl_init(bl_t b, bool srv) */ if (b->b_connected != 1) { bl_log(b->b_fun, LOG_DEBUG, - "%s: connect failed for `%s' (%m)", - __func__, sun->sun_path); + "%s: connect failed for `%s' (%s)", + __func__, sun->sun_path, strerror(errno)); b->b_connected = 1; } BL_UNLOCK(b); @@ -220,8 +220,8 @@ bl_init(bl_t b, bool srv) errno = serrno; if (rv == -1) { bl_log(b->b_fun, LOG_ERR, - "%s: bind failed for `%s' (%m)", - __func__, sun->sun_path); + "%s: bind failed for `%s' (%s)", + __func__, sun->sun_path, strerror(errno)); goto out; } } @@ -260,7 +260,8 @@ bl_init(bl_t b, bool srv) if (setsockopt(b->b_fd, CRED_LEVEL, CRED_NAME, &one, (socklen_t)sizeof(one)) == -1) { bl_log(b->b_fun, LOG_ERR, "%s: setsockopt %s " - "failed (%m)", __func__, __STRING(CRED_NAME)); + "failed (%s)", __func__, __STRING(CRED_NAME), + strerror(errno)); goto out; } #endif @@ -296,7 +297,8 @@ bl_create(bool srv, const char *path, void (*fun)(int, const char *, va_list)) return b; out: free(b); - bl_log(fun, LOG_ERR, "%s: malloc failed (%m)", __func__); + bl_log(fun, LOG_ERR, "%s: malloc failed (%s)", __func__, + strerror(errno)); return NULL; } @@ -451,7 +453,8 @@ bl_recv(bl_t b) rlen = recvmsg(b->b_fd, &msg, 0); if (rlen == -1) { - bl_log(b->b_fun, LOG_ERR, "%s: recvmsg failed (%m)", __func__); + bl_log(b->b_fun, LOG_ERR, "%s: recvmsg failed (%s)", __func__, + strerror(errno)); return NULL; } diff --git a/contrib/elftoolchain/elfcopy/ascii.c b/contrib/elftoolchain/elfcopy/ascii.c index fb1edb3cce46..6adecf8d347a 100644 --- a/contrib/elftoolchain/elfcopy/ascii.c +++ b/contrib/elftoolchain/elfcopy/ascii.c @@ -251,6 +251,7 @@ create_elf_from_srec(struct elfcopy *ecp, int ifd) sec_index = 1; sec_addr = entry = 0; while (fgets(line, _LINE_BUFSZ, ifp) != NULL) { + sz = 0; /* Silence GCC 5.3 uninitialized variable warning */ if (line[0] == '\r' || line[0] == '\n') continue; if (line[0] == '$' && line[1] == '$') { diff --git a/contrib/elftoolchain/libelftc/elftc_bfd_find_target.3 b/contrib/elftoolchain/libelftc/elftc_bfd_find_target.3 index 20dea3cb97d9..c340c0c5b68d 100644 --- a/contrib/elftoolchain/libelftc/elftc_bfd_find_target.3 +++ b/contrib/elftoolchain/libelftc/elftc_bfd_find_target.3 @@ -89,6 +89,7 @@ Known descriptor names and their properties include: .It Li elf64-ia64-big Ta ELF Ta MSB Ta 64 .It Li elf64-ia64-little Ta ELF Ta LSB Ta 64 .It Li elf64-little Ta ELF Ta LSB Ta 64 +.It Li elf64-littleaarch64 Ta ELF Ta LSB Ta 64 .It Li elf64-littlemips Ta ELF Ta LSB Ta 64 .It Li elf64-powerpc Ta ELF Ta MSB Ta 64 .It Li elf64-powerpcle Ta ELF Ta LSB Ta 64 diff --git a/contrib/elftoolchain/libelftc/libelftc_bfdtarget.c b/contrib/elftoolchain/libelftc/libelftc_bfdtarget.c index 88f3220df0b0..d6a031e73090 100644 --- a/contrib/elftoolchain/libelftc/libelftc_bfdtarget.c +++ b/contrib/elftoolchain/libelftc/libelftc_bfdtarget.c @@ -250,6 +250,14 @@ struct _Elftc_Bfd_Target _libelftc_targets[] = { }, { + .bt_name = "elf64-littleaarch64", + .bt_type = ETF_ELF, + .bt_byteorder = ELFDATA2LSB, + .bt_elfclass = ELFCLASS64, + .bt_machine = EM_AARCH64, + }, + + { .bt_name = "elf64-littlemips", .bt_type = ETF_ELF, .bt_byteorder = ELFDATA2LSB, diff --git a/contrib/elftoolchain/libelftc/libelftc_dem_gnu3.c b/contrib/elftoolchain/libelftc/libelftc_dem_gnu3.c index 7409363f73ee..cb73ad3d67f4 100644 --- a/contrib/elftoolchain/libelftc/libelftc_dem_gnu3.c +++ b/contrib/elftoolchain/libelftc/libelftc_dem_gnu3.c @@ -2551,7 +2551,7 @@ again: case 'w': /* wchar_t */ - if (!cpp_demangle_push_str(ddata, "wchar_t", 6)) + if (!cpp_demangle_push_str(ddata, "wchar_t", 7)) goto clean; ++ddata->cur; goto rtn; diff --git a/contrib/elftoolchain/readelf/readelf.c b/contrib/elftoolchain/readelf/readelf.c index 79cb8b76c5d8..79fff4a3a7d2 100644 --- a/contrib/elftoolchain/readelf/readelf.c +++ b/contrib/elftoolchain/readelf/readelf.c @@ -343,7 +343,7 @@ static const char *note_type_openbsd(unsigned int nt); static const char *note_type_unknown(unsigned int nt); static const char *note_type_xen(unsigned int nt); static const char *option_kind(uint8_t kind); -static const char *phdr_type(unsigned int ptype); +static const char *phdr_type(unsigned int mach, unsigned int ptype); static const char *ppc_abi_fp(uint64_t fp); static const char *ppc_abi_vector(uint64_t vec); static void readelf_usage(int status); @@ -622,10 +622,24 @@ elf_ver(unsigned int ver) } static const char * -phdr_type(unsigned int ptype) +phdr_type(unsigned int mach, unsigned int ptype) { static char s_ptype[32]; + if (ptype >= PT_LOPROC && ptype <= PT_HIPROC) { + switch (mach) { + case EM_ARM: + switch (ptype) { + case PT_ARM_ARCHEXT: return "ARM_ARCHEXT"; + case PT_ARM_EXIDX: return "ARM_EXIDX"; + } + break; + } + snprintf(s_ptype, sizeof(s_ptype), "LOPROC+%#x", + ptype - PT_LOPROC); + return (s_ptype); + } + switch (ptype) { case PT_NULL: return "NULL"; case PT_LOAD: return "LOAD"; @@ -639,10 +653,7 @@ phdr_type(unsigned int ptype) case PT_GNU_STACK: return "GNU_STACK"; case PT_GNU_RELRO: return "GNU_RELRO"; default: - if (ptype >= PT_LOPROC && ptype <= PT_HIPROC) - snprintf(s_ptype, sizeof(s_ptype), "LOPROC+%#x", - ptype - PT_LOPROC); - else if (ptype >= PT_LOOS && ptype <= PT_HIOS) + if (ptype >= PT_LOOS && ptype <= PT_HIOS) snprintf(s_ptype, sizeof(s_ptype), "LOOS+%#x", ptype - PT_LOOS); else @@ -659,6 +670,15 @@ section_type(unsigned int mach, unsigned int stype) if (stype >= SHT_LOPROC && stype <= SHT_HIPROC) { switch (mach) { + case EM_ARM: + switch (stype) { + case SHT_ARM_EXIDX: return "ARM_EXIDX"; + case SHT_ARM_PREEMPTMAP: return "ARM_PREEMPTMAP"; + case SHT_ARM_ATTRIBUTES: return "ARM_ATTRIBUTES"; + case SHT_ARM_DEBUGOVERLAY: return "ARM_DEBUGOVERLAY"; + case SHT_ARM_OVERLAYSECTION: return "ARM_OVERLAYSECTION"; + } + break; case EM_X86_64: switch (stype) { case SHT_X86_64_UNWIND: return "X86_64_UNWIND"; @@ -2273,9 +2293,10 @@ dump_phdr(struct readelf *re) #define PH_HDR "Type", "Offset", "VirtAddr", "PhysAddr", "FileSiz", \ "MemSiz", "Flg", "Align" -#define PH_CT phdr_type(phdr.p_type), (uintmax_t)phdr.p_offset, \ - (uintmax_t)phdr.p_vaddr, (uintmax_t)phdr.p_paddr, \ - (uintmax_t)phdr.p_filesz, (uintmax_t)phdr.p_memsz, \ +#define PH_CT phdr_type(re->ehdr.e_machine, phdr.p_type), \ + (uintmax_t)phdr.p_offset, (uintmax_t)phdr.p_vaddr, \ + (uintmax_t)phdr.p_paddr, (uintmax_t)phdr.p_filesz, \ + (uintmax_t)phdr.p_memsz, \ phdr.p_flags & PF_R ? 'R' : ' ', \ phdr.p_flags & PF_W ? 'W' : ' ', \ phdr.p_flags & PF_X ? 'E' : ' ', \ diff --git a/contrib/gcc/config/arm/libunwind.S b/contrib/gcc/config/arm/libunwind-arm.S index 8b1e2f3722e4..8b1e2f3722e4 100644 --- a/contrib/gcc/config/arm/libunwind.S +++ b/contrib/gcc/config/arm/libunwind-arm.S diff --git a/contrib/libarchive/cat/test/test_version.c b/contrib/libarchive/cat/test/test_version.c index e7c93630b499..e587b3440c6d 100644 --- a/contrib/libarchive/cat/test/test_version.c +++ b/contrib/libarchive/cat/test/test_version.c @@ -83,7 +83,7 @@ DEFINE_TEST(test_version) if (*q == 'a' || *q == 'b' || *q == 'c' || *q == 'd') ++q; /* Skip arbitrary third-party version numbers. */ - while (s > 0 && (*q == ' ' || *q == '/' || *q == '.' || isalnum(*q))) { + while (s > 0 && (*q == ' ' || *q == '-' || *q == '/' || *q == '.' || isalnum(*q))) { ++q; --s; } diff --git a/contrib/libarchive/cpio/cmdline.c b/contrib/libarchive/cpio/cmdline.c index e30a898fafc0..f37fe5e8431e 100644 --- a/contrib/libarchive/cpio/cmdline.c +++ b/contrib/libarchive/cpio/cmdline.c @@ -63,6 +63,7 @@ static const struct option { } cpio_longopts[] = { { "b64encode", 0, OPTION_B64ENCODE }, { "create", 0, 'o' }, + { "dereference", 0, 'L' }, { "dot", 0, 'V' }, { "extract", 0, 'i' }, { "file", 1, 'F' }, diff --git a/contrib/libarchive/cpio/test/test_option_version.c b/contrib/libarchive/cpio/test/test_option_version.c index 32ba3000477e..ac58cefda11f 100644 --- a/contrib/libarchive/cpio/test/test_option_version.c +++ b/contrib/libarchive/cpio/test/test_option_version.c @@ -75,7 +75,7 @@ verify(const char *p, size_t s) if (*q == 'a' || *q == 'b' || *q == 'c' || *q == 'd') ++q; /* Skip arbitrary third-party version numbers. */ - while (s > 0 && (*q == ' ' || *q == '/' || *q == '.' || isalnum(*q))) { + while (s > 0 && (*q == ' ' || *q == '-' || *q == '/' || *q == '.' || isalnum(*q))) { ++q; --s; } diff --git a/contrib/libarchive/libarchive/archive_match.c b/contrib/libarchive/libarchive/archive_match.c index 4c41badf1f86..0719cbd54736 100644 --- a/contrib/libarchive/libarchive/archive_match.c +++ b/contrib/libarchive/libarchive/archive_match.c @@ -655,7 +655,7 @@ add_pattern_from_file(struct archive_match *a, struct match_list *mlist, } } - /* If something error happend, report it immediately. */ + /* If an error occurred, report it immediately. */ if (r < ARCHIVE_OK) { archive_copy_error(&(a->archive), ar); archive_read_free(ar); diff --git a/contrib/libarchive/libarchive/archive_ppmd7_private.h b/contrib/libarchive/libarchive/archive_ppmd7_private.h index 3a6b9eb4190f..06c99e828ab6 100644 --- a/contrib/libarchive/libarchive/archive_ppmd7_private.h +++ b/contrib/libarchive/libarchive/archive_ppmd7_private.h @@ -19,7 +19,7 @@ If you need the compatibility with original PPMd var.H, you can use external Ran #define PPMD7_MAX_ORDER 64 #define PPMD7_MIN_MEM_SIZE (1 << 11) -#define PPMD7_MAX_MEM_SIZE (0xFFFFFFFF - 12 * 3) +#define PPMD7_MAX_MEM_SIZE (0xFFFFFFFFu - 12 * 3) struct CPpmd7_Context_; diff --git a/contrib/libarchive/libarchive/archive_read_add_passphrase.c b/contrib/libarchive/libarchive/archive_read_add_passphrase.c index f67f1ebc6e27..cf821b5d483c 100644 --- a/contrib/libarchive/libarchive/archive_read_add_passphrase.c +++ b/contrib/libarchive/libarchive/archive_read_add_passphrase.c @@ -125,7 +125,7 @@ void __archive_read_reset_passphrase(struct archive_read *a) { - a->passphrases.candiate = -1; + a->passphrases.candidate = -1; } /* @@ -137,31 +137,31 @@ __archive_read_next_passphrase(struct archive_read *a) struct archive_read_passphrase *p; const char *passphrase; - if (a->passphrases.candiate < 0) { + if (a->passphrases.candidate < 0) { /* Count out how many passphrases we have. */ int cnt = 0; for (p = a->passphrases.first; p != NULL; p = p->next) cnt++; - a->passphrases.candiate = cnt; + a->passphrases.candidate = cnt; p = a->passphrases.first; - } else if (a->passphrases.candiate > 1) { + } else if (a->passphrases.candidate > 1) { /* Rotate a passphrase list. */ - a->passphrases.candiate--; + a->passphrases.candidate--; p = remove_passphrases_from_head(a); add_passphrase_to_tail(a, p); - /* Pick a new passphrase candiate up. */ + /* Pick a new passphrase candidate up. */ p = a->passphrases.first; - } else if (a->passphrases.candiate == 1) { - /* This case is that all cadiates failed to decryption. */ - a->passphrases.candiate = 0; + } else if (a->passphrases.candidate == 1) { + /* This case is that all candidates failed to decrypt. */ + a->passphrases.candidate = 0; if (a->passphrases.first->next != NULL) { /* Rotate a passphrase list. */ p = remove_passphrases_from_head(a); add_passphrase_to_tail(a, p); } p = NULL; - } else /* There is no passphrase candaite. */ + } else /* There is no passphrase candidate. */ p = NULL; if (p != NULL) @@ -177,7 +177,7 @@ __archive_read_next_passphrase(struct archive_read *a) if (p == NULL) return (NULL); insert_passphrase_to_head(a, p); - a->passphrases.candiate = 1; + a->passphrases.candidate = 1; } } else passphrase = NULL; diff --git a/contrib/libarchive/libarchive/archive_read_disk_entry_from_file.c b/contrib/libarchive/libarchive/archive_read_disk_entry_from_file.c index cf8ea2ef2a10..29b4b6cb0869 100644 --- a/contrib/libarchive/libarchive/archive_read_disk_entry_from_file.c +++ b/contrib/libarchive/libarchive/archive_read_disk_entry_from_file.c @@ -641,13 +641,16 @@ translate_acl(struct archive_read_disk *a, * Libarchive stores "flag" (NFSv4 inheritance bits) * in the ae_perm bitmap. */ - acl_get_flagset_np(acl_entry, &acl_flagset); - for (i = 0; i < (int)(sizeof(acl_inherit_map) / sizeof(acl_inherit_map[0])); ++i) { - if (acl_get_flag_np(acl_flagset, - acl_inherit_map[i].platform_inherit)) - ae_perm |= acl_inherit_map[i].archive_inherit; - - } + // XXX acl_get_flagset_np on FreeBSD returns EINVAL for + // non-NFSv4 ACLs + r = acl_get_flagset_np(acl_entry, &acl_flagset); + if (r == 0) { + for (i = 0; i < (int)(sizeof(acl_inherit_map) / sizeof(acl_inherit_map[0])); ++i) { + if (acl_get_flag_np(acl_flagset, + acl_inherit_map[i].platform_inherit)) + ae_perm |= acl_inherit_map[i].archive_inherit; + } + } #endif acl_get_permset(acl_entry, &acl_permset); diff --git a/contrib/libarchive/libarchive/archive_read_disk_posix.c b/contrib/libarchive/libarchive/archive_read_disk_posix.c index f54cda69c125..5901a879c497 100644 --- a/contrib/libarchive/libarchive/archive_read_disk_posix.c +++ b/contrib/libarchive/libarchive/archive_read_disk_posix.c @@ -938,7 +938,7 @@ next_entry(struct archive_read_disk *a, struct tree *t, r = archive_match_path_excluded(a->matching, entry); if (r < 0) { archive_set_error(&(a->archive), errno, - "Faild : %s", archive_error_string(a->matching)); + "Failed : %s", archive_error_string(a->matching)); return (r); } if (r) { @@ -1041,7 +1041,7 @@ next_entry(struct archive_read_disk *a, struct tree *t, r = archive_match_time_excluded(a->matching, entry); if (r < 0) { archive_set_error(&(a->archive), errno, - "Faild : %s", archive_error_string(a->matching)); + "Failed : %s", archive_error_string(a->matching)); return (r); } if (r) { @@ -1067,7 +1067,7 @@ next_entry(struct archive_read_disk *a, struct tree *t, r = archive_match_owner_excluded(a->matching, entry); if (r < 0) { archive_set_error(&(a->archive), errno, - "Faild : %s", archive_error_string(a->matching)); + "Failed : %s", archive_error_string(a->matching)); return (r); } if (r) { diff --git a/contrib/libarchive/libarchive/archive_read_private.h b/contrib/libarchive/libarchive/archive_read_private.h index b181569ce229..7fa5b24c1646 100644 --- a/contrib/libarchive/libarchive/archive_read_private.h +++ b/contrib/libarchive/libarchive/archive_read_private.h @@ -221,7 +221,7 @@ struct archive_read { struct { struct archive_read_passphrase *first; struct archive_read_passphrase **last; - int candiate; + int candidate; archive_passphrase_callback *callback; void *client_data; } passphrases; diff --git a/contrib/libarchive/libarchive/archive_read_support_filter_lz4.c b/contrib/libarchive/libarchive/archive_read_support_filter_lz4.c index e877917b940b..37b2f59004b1 100644 --- a/contrib/libarchive/libarchive/archive_read_support_filter_lz4.c +++ b/contrib/libarchive/libarchive/archive_read_support_filter_lz4.c @@ -595,7 +595,7 @@ lz4_filter_read_data_block(struct archive_read_filter *self, const void **p) #endif } - /* Check if an error happend in decompression process. */ + /* Check if an error occurred in the decompression process. */ if (uncompressed_size < 0) { archive_set_error(&(self->archive->archive), ARCHIVE_ERRNO_MISC, "lz4 decompression failed"); diff --git a/contrib/libarchive/libarchive/archive_read_support_format_lha.c b/contrib/libarchive/libarchive/archive_read_support_format_lha.c index dbfc1cd87c86..a7f1d8d949f5 100644 --- a/contrib/libarchive/libarchive/archive_read_support_format_lha.c +++ b/contrib/libarchive/libarchive/archive_read_support_format_lha.c @@ -1715,8 +1715,11 @@ lha_crc16(uint16_t crc, const void *pp, size_t len) #undef bswap16 #if defined(_MSC_VER) && _MSC_VER >= 1400 /* Visual Studio */ # define bswap16(x) _byteswap_ushort(x) -#elif (defined(__GNUC__) && __GNUC__ >= 4 && __GNUC_MINOR__ >= 8) \ - || defined(__clang__) +#elif defined(__GNUC__) && ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || __GNUC__ > 4) +/* GCC 4.8 and later has __builtin_bswap16() */ +# define bswap16(x) __builtin_bswap16(x) +#elif defined(__clang__) +/* All clang versions have __builtin_bswap16() */ # define bswap16(x) __builtin_bswap16(x) #else # define bswap16(x) ((((x) >> 8) & 0xff) | ((x) << 8)) diff --git a/contrib/libarchive/libarchive/archive_read_support_format_warc.c b/contrib/libarchive/libarchive/archive_read_support_format_warc.c index 9d8013287568..deeaa9e6d93d 100644 --- a/contrib/libarchive/libarchive/archive_read_support_format_warc.c +++ b/contrib/libarchive/libarchive/archive_read_support_format_warc.c @@ -318,7 +318,7 @@ start_over: } memcpy(w->pool.str, fnam.str, fnam.len); w->pool.str[fnam.len] = '\0'; - /* let noone else know about the pool, it's a secret, shhh */ + /* let no one else know about the pool, it's a secret, shhh */ fnam.str = w->pool.str; /* snarf mtime or deduce from rtime diff --git a/contrib/libarchive/libarchive/archive_util.c b/contrib/libarchive/libarchive/archive_util.c index b7ea74953dad..05f17c5b6de7 100644 --- a/contrib/libarchive/libarchive/archive_util.c +++ b/contrib/libarchive/libarchive/archive_util.c @@ -580,7 +580,7 @@ void __archive_ensure_cloexec_flag(int fd) { #if defined(_WIN32) && !defined(__CYGWIN__) - (void)fd; /* UNSED */ + (void)fd; /* UNUSED */ #else int flags; diff --git a/contrib/libarchive/libarchive/archive_write_disk_acl.c b/contrib/libarchive/libarchive/archive_write_disk_acl.c index 5cbba54f08fd..54a96696f285 100644 --- a/contrib/libarchive/libarchive/archive_write_disk_acl.c +++ b/contrib/libarchive/libarchive/archive_write_disk_acl.c @@ -145,7 +145,7 @@ set_acl(struct archive *a, int fd, const char *name, gid_t ae_gid; const char *ae_name; int entries; - int i; + int i, r; ret = ARCHIVE_OK; entries = archive_acl_reset(abstract_acl, ae_requested_type); @@ -223,12 +223,16 @@ set_acl(struct archive *a, int fd, const char *name, } #ifdef ACL_TYPE_NFS4 - acl_get_flagset_np(acl_entry, &acl_flagset); - acl_clear_flags_np(acl_flagset); - for (i = 0; i < (int)(sizeof(acl_inherit_map) / sizeof(acl_inherit_map[0])); ++i) { - if (ae_permset & acl_inherit_map[i].archive_inherit) - acl_add_flag_np(acl_flagset, - acl_inherit_map[i].platform_inherit); + // XXX acl_get_flagset_np on FreeBSD returns EINVAL for + // non-NFSv4 ACLs + r = acl_get_flagset_np(acl_entry, &acl_flagset); + if (r == 0) { + acl_clear_flags_np(acl_flagset); + for (i = 0; i < (int)(sizeof(acl_inherit_map) / sizeof(acl_inherit_map[0])); ++i) { + if (ae_permset & acl_inherit_map[i].archive_inherit) + acl_add_flag_np(acl_flagset, + acl_inherit_map[i].platform_inherit); + } } #endif } diff --git a/contrib/libarchive/libarchive/archive_write_disk_posix.c b/contrib/libarchive/libarchive/archive_write_disk_posix.c index 74c7f6ac8cd6..a60d225f5c0e 100644 --- a/contrib/libarchive/libarchive/archive_write_disk_posix.c +++ b/contrib/libarchive/libarchive/archive_write_disk_posix.c @@ -1796,7 +1796,7 @@ edit_deep_directories(struct archive_write_disk *a) char *tail = a->name; /* If path is short, avoid the open() below. */ - if (strlen(tail) <= PATH_MAX) + if (strlen(tail) < PATH_MAX) return; /* Try to record our starting dir. */ @@ -1806,7 +1806,7 @@ edit_deep_directories(struct archive_write_disk *a) return; /* As long as the path is too long... */ - while (strlen(tail) > PATH_MAX) { + while (strlen(tail) >= PATH_MAX) { /* Locate a dir prefix shorter than PATH_MAX. */ tail += PATH_MAX - 8; while (tail > a->name && *tail != '/') diff --git a/contrib/libarchive/libarchive/archive_write_set_format_iso9660.c b/contrib/libarchive/libarchive/archive_write_set_format_iso9660.c index cb3e54e8d21b..c20e0885236e 100644 --- a/contrib/libarchive/libarchive/archive_write_set_format_iso9660.c +++ b/contrib/libarchive/libarchive/archive_write_set_format_iso9660.c @@ -436,7 +436,7 @@ struct iso_option { * Type : string * Default: Auto detect * : We check a size of boot image; - * : If ths size is just 1.22M/1.44M/2.88M, + * : If the size is just 1.22M/1.44M/2.88M, * : we assume boot_type is 'fd'; * : otherwise boot_type is 'no-emulation'. * COMPAT : diff --git a/contrib/libarchive/libarchive/archive_write_set_format_ustar.c b/contrib/libarchive/libarchive/archive_write_set_format_ustar.c index 7f868f1c15cf..a9e6dd7fe3a1 100644 --- a/contrib/libarchive/libarchive/archive_write_set_format_ustar.c +++ b/contrib/libarchive/libarchive/archive_write_set_format_ustar.c @@ -307,7 +307,7 @@ archive_write_ustar_header(struct archive_write *a, struct archive_entry *entry) * case getting WCS failed. On POSIX, this is a * normal operation. */ - if (p != NULL && p[strlen(p) - 1] != '/') { + if (p != NULL && p[0] != '\0' && p[strlen(p) - 1] != '/') { struct archive_string as; archive_string_init(&as); diff --git a/contrib/libarchive/libarchive/test/main.c b/contrib/libarchive/libarchive/test/main.c index fb53aaef0229..b9aa865e4b05 100644 --- a/contrib/libarchive/libarchive/test/main.c +++ b/contrib/libarchive/libarchive/test/main.c @@ -1440,6 +1440,31 @@ assertion_file_size(const char *file, int line, const char *pathname, long size) return (0); } +/* Verify mode of 'pathname'. */ +int +assertion_file_mode(const char *file, int line, const char *pathname, int expected_mode) +{ + int mode; + int r; + + assertion_count(file, line); +#if defined(_WIN32) && !defined(__CYGWIN__) + failure_start(file, line, "assertFileMode not yet implemented for Windows"); +#else + { + struct stat st; + r = lstat(pathname, &st); + mode = (int)(st.st_mode & 0777); + } + if (r == 0 && mode == expected_mode) + return (1); + failure_start(file, line, "File %s has mode %o, expected %o", + pathname, mode, expected_mode); +#endif + failure_finish(NULL); + return (0); +} + /* Assert that 'pathname' is a dir. If mode >= 0, verify that too. */ int assertion_is_dir(const char *file, int line, const char *pathname, int mode) diff --git a/contrib/libarchive/libarchive/test/test.h b/contrib/libarchive/libarchive/test/test.h index 1f316bd5170f..bcf68690c405 100644 --- a/contrib/libarchive/libarchive/test/test.h +++ b/contrib/libarchive/libarchive/test/test.h @@ -182,6 +182,8 @@ assertion_file_nlinks(__FILE__, __LINE__, pathname, nlinks) #define assertFileSize(pathname, size) \ assertion_file_size(__FILE__, __LINE__, pathname, size) +#define assertFileMode(pathname, mode) \ + assertion_file_mode(__FILE__, __LINE__, pathname, mode) #define assertTextFileContents(text, pathname) \ assertion_text_file_contents(__FILE__, __LINE__, text, pathname) #define assertFileContainsLinesAnyOrder(pathname, lines) \ @@ -246,6 +248,7 @@ int assertion_file_mtime_recent(const char *, int, const char *); int assertion_file_nlinks(const char *, int, const char *, int); int assertion_file_not_exists(const char *, int, const char *); int assertion_file_size(const char *, int, const char *, long); +int assertion_file_mode(const char *, int, const char *, int); int assertion_is_dir(const char *, int, const char *, int); int assertion_is_hardlink(const char *, int, const char *, const char *); int assertion_is_not_hardlink(const char *, int, const char *, const char *); diff --git a/contrib/libarchive/libarchive/test/test_archive_string_conversion.c b/contrib/libarchive/libarchive/test/test_archive_string_conversion.c index fea141d4ab0d..e86f97c8a492 100644 --- a/contrib/libarchive/libarchive/test/test_archive_string_conversion.c +++ b/contrib/libarchive/libarchive/test/test_archive_string_conversion.c @@ -800,8 +800,8 @@ DEFINE_TEST(test_archive_string_conversion) assertEqualIntA(a, ARCHIVE_OK, archive_read_next_header(a, &ae)); assert((fp = fopen(testdata, "w")) != NULL); while ((size = archive_read_data(a, buff, 512)) > 0) - fwrite(buff, 1, size, fp); - fclose(fp); + assertEqualInt(size, fwrite(buff, 1, size, fp)); + assertEqualInt(0, fclose(fp)); assertEqualInt(ARCHIVE_OK, archive_read_free(a)); test_archive_string_normalization_nfc(testdata); diff --git a/contrib/libarchive/libarchive/test/test_fuzz.c b/contrib/libarchive/libarchive/test/test_fuzz.c index 0328b6cb37ce..67aa1aca8d75 100644 --- a/contrib/libarchive/libarchive/test/test_fuzz.c +++ b/contrib/libarchive/libarchive/test/test_fuzz.c @@ -110,13 +110,17 @@ test_fuzz(const struct files *filesets) for (i = 0; filesets[n].names[i] != NULL; ++i) { tmp = slurpfile(&size, filesets[n].names[i]); - rawimage = (char *)realloc(rawimage, oldsize + size); + char *newraw = (char *)realloc(rawimage, oldsize + size); + if (!assert(newraw != NULL)) + { + free(rawimage); + continue; + } + rawimage = newraw; memcpy(rawimage + oldsize, tmp, size); oldsize += size; size = oldsize; free(tmp); - if (!assert(rawimage != NULL)) - continue; } } if (size == 0) diff --git a/contrib/libarchive/libarchive/test/test_read_format_rar.c b/contrib/libarchive/libarchive/test/test_read_format_rar.c index 587032309c47..6392d8f50ff8 100644 --- a/contrib/libarchive/libarchive/test/test_read_format_rar.c +++ b/contrib/libarchive/libarchive/test/test_read_format_rar.c @@ -3603,7 +3603,7 @@ DEFINE_TEST(test_read_format_rar_multivolume_uncompressed_files) assertEqualIntA(a, 0, archive_read_data(a, buff, sizeof(buff))); /* - * Eigth header. + * Eighth header. */ assertA(0 == archive_read_next_header(a, &ae)); assertEqualString("testdir/testsymlink6", archive_entry_pathname(ae)); diff --git a/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.c b/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.c new file mode 100644 index 000000000000..6c8aa8eee1b2 --- /dev/null +++ b/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.c @@ -0,0 +1,143 @@ +/*- + * Copyright (c) 2016 Tim Kientzle + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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. + */ +#include "test.h" +__FBSDID("$FreeBSD"); + +#include <locale.h> + + +/* + * Github Issue 748 reported problems with end-of-entry handling + * with highly-compressible data. This resulted in the end of the + * data being truncated (extracted as zero bytes). + */ + +/* + * Extract the specific test archive that was used to diagnose + * Issue 748: + */ +DEFINE_TEST(test_read_format_zip_high_compression) +{ + const char *refname = "test_read_format_zip_high_compression.zip"; + char *p; + size_t archive_size; + struct archive *a; + struct archive_entry *entry; + + const void *pv; + size_t s; + int64_t o; + + extract_reference_file(refname); + p = slurpfile(&archive_size, refname); + + assert((a = archive_read_new()) != NULL); + assertEqualIntA(a, ARCHIVE_OK, archive_read_support_format_zip(a)); + assertEqualIntA(a, ARCHIVE_OK, read_open_memory_seek(a, p, archive_size, 16 * 1024)); + assertEqualInt(ARCHIVE_OK, archive_read_next_header(a, &entry)); + + assertEqualInt(ARCHIVE_OK, archive_read_data_block(a, &pv, &s, &o)); + assertEqualInt(262144, s); + assertEqualInt(0, o); + + assertEqualInt(ARCHIVE_OK, archive_read_data_block(a, &pv, &s, &o)); + assertEqualInt(160, s); + assertEqualInt(262144, o); + + assertEqualInt(ARCHIVE_EOF, archive_read_data_block(a, &pv, &s, &o)); + + assertEqualInt(ARCHIVE_OK, archive_free(a)); + free(p); +} + +/* + * Synthesize a lot of varying inputs that are highly compressible. + */ +DEFINE_TEST(test_read_format_zip_high_compression2) +{ + const size_t body_size = 1024 * 1024; + const size_t buff_size = 2 * 1024 * 1024; + char *body, *body_read, *buff; + int n; + + assert((body = malloc(body_size)) != NULL); + assert((body_read = malloc(body_size)) != NULL); + assert((buff = malloc(buff_size)) != NULL); + + /* Highly-compressible data: all bytes 255, except for a + * single 1 byte. + * The body is always 256k + 6 bytes long (the internal deflation + * buffer is exactly 256k). + */ + + for(n = 1024; n < (int)body_size; n += 1024) { + struct archive *a; + struct archive_entry *entry; + size_t used = 0; + const void *pv; + size_t s; + int64_t o; + + memset(body, 255, body_size); + body[n] = 1; + + /* Write an archive with a single entry of n bytes. */ + assert((a = archive_write_new()) != NULL); + assertEqualInt(ARCHIVE_OK, archive_write_set_format_zip(a)); + assertEqualInt(ARCHIVE_OK, archive_write_open_memory(a, buff, buff_size, &used)); + + entry = archive_entry_new2(a); + archive_entry_set_pathname(entry, "test"); + archive_entry_set_filetype(entry, AE_IFREG); + archive_entry_set_size(entry, 262150); + assertEqualInt(ARCHIVE_OK, archive_write_header(a, entry)); + archive_entry_free(entry); + assertEqualInt(262150, archive_write_data(a, body, 262150)); + assertEqualInt(ARCHIVE_OK, archive_write_free(a)); + + /* Read back the entry and verify the contents. */ + assert((a = archive_read_new()) != NULL); + assertEqualIntA(a, ARCHIVE_OK, archive_read_support_format_all(a)); + assertEqualIntA(a, ARCHIVE_OK, archive_read_support_filter_all(a)); + assertEqualIntA(a, ARCHIVE_OK, read_open_memory(a, buff, used, 17)); + assertEqualInt(ARCHIVE_OK, archive_read_next_header(a, &entry)); + + assertEqualInt(ARCHIVE_OK, archive_read_data_block(a, &pv, &s, &o)); + assertEqualInt(262144, s); + assertEqualInt(0, o); + + assertEqualInt(ARCHIVE_OK, archive_read_data_block(a, &pv, &s, &o)); + assertEqualInt(6, s); + assertEqualInt(262144, o); + + assertEqualInt(ARCHIVE_EOF, archive_read_data_block(a, &pv, &s, &o)); + + assertEqualInt(ARCHIVE_OK, archive_free(a)); + } + + free(body); + free(body_read); + free(buff); +} diff --git a/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.zip.uu b/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.zip.uu new file mode 100644 index 000000000000..094288033d97 --- /dev/null +++ b/contrib/libarchive/libarchive/test/test_read_format_zip_high_compression.zip.uu @@ -0,0 +1,18 @@ +begin 644 test_read_format_zip_high_compression.zip +M4$L#!!0`"``(`*=Y]4@``````````*``!``(`"``8VAA<BYB:6Y55`T`!\L> +MD5>>))%7GB215W5X"P`!!/8!```$%````.W=06K#,!`%T&E)P8LL?*2XC@N% +M)#5QO>AM<K0<+2=0:!OBP>@9WDJ6!%\6$K/Q6T3LAX]N/GQ'Z9G&KA^*K1'S +M.`[GOIM*[TP_Q_>O0[G_:3X.Y\^^V/X2<<GT&IM=$]OK?[71_LJ],3;1+*(T +M_U)99\T+````````````````````````````````````````L`:E?]*S#FVT +MJY:='SPB>_]DR\X?`("_R:X_U"Y[_:F;;Q``ZN+L!P"H3W;]$_5G`&!9V?</ +M````X/FRZP_9LO,'@`S9YR^0P_Z'NF7?/P`````````````````````````` +M```````````````````````````````````````````````````````````` +M```````````````````````````````````````````````````````````` +M```````````````````````````````````````````````````````````` +M```````````````````````````````````````````````````````````` +MJ%L3VVM-LO,&8/UN4$L'"!<='%^U`0``H``$`%!+`0(4`Q0`"``(`*=Y]4@7 +M'1Q?M0$``*``!``(`"````````````"D@0````!C:&%R+F)I;E54#0`'RQZ1 +M5YXDD5>>))%7=7@+``$$]@$```04````4$L%!@`````!``$`5@````L"```` +!```` +` +end diff --git a/contrib/libarchive/libarchive/test/test_write_disk_secure744.c b/contrib/libarchive/libarchive/test/test_write_disk_secure744.c new file mode 100644 index 000000000000..08c725e12b80 --- /dev/null +++ b/contrib/libarchive/libarchive/test/test_write_disk_secure744.c @@ -0,0 +1,95 @@ +/*- + * Copyright (c) 2003-2007,2016 Tim Kientzle + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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. + */ +#include "test.h" +__FBSDID("$FreeBSD$"); + +#define UMASK 022 + +/* + * Github Issue #744 describes a bug in the sandboxing code that + * causes very long pathnames to not get checked for symlinks. + */ + +DEFINE_TEST(test_write_disk_secure744) +{ +#if defined(_WIN32) && !defined(__CYGWIN__) + skipping("archive_write_disk security checks not supported on Windows"); +#else + struct archive *a; + struct archive_entry *ae; + size_t buff_size = 8192; + char *buff = malloc(buff_size); + char *p = buff; + int n = 0; + int t; + + assert(buff != NULL); + + /* Start with a known umask. */ + assertUmask(UMASK); + + /* Create an archive_write_disk object. */ + assert((a = archive_write_disk_new()) != NULL); + archive_write_disk_set_options(a, ARCHIVE_EXTRACT_SECURE_SYMLINKS); + + while (p + 500 < buff + buff_size) { + memset(p, 'x', 100); + p += 100; + p[0] = '\0'; + + buff[0] = ((n / 1000) % 10) + '0'; + buff[1] = ((n / 100) % 10)+ '0'; + buff[2] = ((n / 10) % 10)+ '0'; + buff[3] = ((n / 1) % 10)+ '0'; + buff[4] = '_'; + ++n; + + /* Create a symlink pointing to the testworkdir */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, buff); + archive_entry_set_mode(ae, S_IFREG | 0777); + archive_entry_copy_symlink(ae, testworkdir); + assertEqualIntA(a, ARCHIVE_OK, archive_write_header(a, ae)); + archive_entry_free(ae); + + *p++ = '/'; + sprintf(p, "target%d", n); + + /* Try to create a file through the symlink, should fail. */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, buff); + archive_entry_set_mode(ae, S_IFDIR | 0777); + + t = archive_write_header(a, ae); + archive_entry_free(ae); + failure("Attempt to create target%d via %d-character symlink should have failed", n, (int)strlen(buff)); + if(!assertEqualInt(ARCHIVE_FAILED, t)) { + break; + } + } + archive_free(a); + free(buff); +#endif +} diff --git a/contrib/libarchive/libarchive/test/test_write_disk_secure745.c b/contrib/libarchive/libarchive/test/test_write_disk_secure745.c new file mode 100644 index 000000000000..fa6939b8cedc --- /dev/null +++ b/contrib/libarchive/libarchive/test/test_write_disk_secure745.c @@ -0,0 +1,76 @@ +/*- + * Copyright (c) 2003-2007,2016 Tim Kientzle + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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. + */ +#include "test.h" +__FBSDID("$FreeBSD$"); + +#define UMASK 022 + +/* + * Github Issue #745 describes a bug in the sandboxing code that + * allows one to use a symlink to edit the permissions on a file or + * directory outside of the sandbox. + */ + +DEFINE_TEST(test_write_disk_secure745) +{ +#if defined(_WIN32) && !defined(__CYGWIN__) + skipping("archive_write_disk security checks not supported on Windows"); +#else + struct archive *a; + struct archive_entry *ae; + + /* Start with a known umask. */ + assertUmask(UMASK); + + /* Create an archive_write_disk object. */ + assert((a = archive_write_disk_new()) != NULL); + archive_write_disk_set_options(a, ARCHIVE_EXTRACT_SECURE_SYMLINKS); + + /* The target dir: The one we're going to try to change permission on */ + assertMakeDir("target", 0700); + + /* The sandbox dir we're going to run inside of. */ + assertMakeDir("sandbox", 0700); + assertChdir("sandbox"); + + /* Create a symlink pointing to the target directory */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, "sym"); + archive_entry_set_mode(ae, S_IFREG | 0777); + archive_entry_copy_symlink(ae, "../target"); + assert(0 == archive_write_header(a, ae)); + archive_entry_free(ae); + + /* Try to alter the target dir through the symlink; this should fail. */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, "sym"); + archive_entry_set_mode(ae, S_IFDIR | 0777); + assert(0 == archive_write_header(a, ae)); + archive_entry_free(ae); + + /* Permission of target dir should not have changed. */ + assertFileMode("../target", 0700); +#endif +} diff --git a/contrib/libarchive/libarchive/test/test_write_disk_secure746.c b/contrib/libarchive/libarchive/test/test_write_disk_secure746.c new file mode 100644 index 000000000000..0daf1b09aaa8 --- /dev/null +++ b/contrib/libarchive/libarchive/test/test_write_disk_secure746.c @@ -0,0 +1,125 @@ +/*- + * Copyright (c) 2003-2007,2016 Tim Kientzle + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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. + */ +#include "test.h" +__FBSDID("$FreeBSD$"); + +#define UMASK 022 + +/* + * Github Issue #746 describes a problem in which hardlink targets are + * not adequately checked and can be used to modify entries outside of + * the sandbox. + */ + +/* + * Verify that ARCHIVE_EXTRACT_SECURE_NODOTDOT disallows '..' in hardlink + * targets. + */ +DEFINE_TEST(test_write_disk_secure746a) +{ +#if defined(_WIN32) && !defined(__CYGWIN__) + skipping("archive_write_disk security checks not supported on Windows"); +#else + struct archive *a; + struct archive_entry *ae; + + /* Start with a known umask. */ + assertUmask(UMASK); + + /* The target directory we're going to try to affect. */ + assertMakeDir("target", 0700); + assertMakeFile("target/foo", 0700, "unmodified"); + + /* The sandbox dir we're going to work within. */ + assertMakeDir("sandbox", 0700); + assertChdir("sandbox"); + + /* Create an archive_write_disk object. */ + assert((a = archive_write_disk_new()) != NULL); + archive_write_disk_set_options(a, ARCHIVE_EXTRACT_SECURE_NODOTDOT); + + /* Attempt to hardlink to the target directory. */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, "bar"); + archive_entry_set_mode(ae, S_IFREG | 0777); + archive_entry_set_size(ae, 8); + archive_entry_copy_hardlink(ae, "../target/foo"); + assertEqualInt(ARCHIVE_FAILED, archive_write_header(a, ae)); + assertEqualInt(ARCHIVE_FAILED, archive_write_data(a, "modified", 8)); + archive_entry_free(ae); + + /* Verify that target file contents are unchanged. */ + assertTextFileContents("unmodified", "../target/foo"); +#endif +} + +/* + * Verify that ARCHIVE_EXTRACT_SECURE_NOSYMLINK disallows symlinks in hardlink + * targets. + */ +DEFINE_TEST(test_write_disk_secure746b) +{ +#if defined(_WIN32) && !defined(__CYGWIN__) + skipping("archive_write_disk security checks not supported on Windows"); +#else + struct archive *a; + struct archive_entry *ae; + + /* Start with a known umask. */ + assertUmask(UMASK); + + /* The target directory we're going to try to affect. */ + assertMakeDir("target", 0700); + assertMakeFile("target/foo", 0700, "unmodified"); + + /* The sandbox dir we're going to work within. */ + assertMakeDir("sandbox", 0700); + assertChdir("sandbox"); + + /* Create an archive_write_disk object. */ + assert((a = archive_write_disk_new()) != NULL); + archive_write_disk_set_options(a, ARCHIVE_EXTRACT_SECURE_SYMLINKS); + + /* Create a symlink to the target directory. */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, "symlink"); + archive_entry_copy_symlink(ae, "../target"); + assertEqualInt(ARCHIVE_FAILED, archive_write_header(a, ae)); + archive_entry_free(ae); + + /* Attempt to hardlink to the target directory via the symlink. */ + assert((ae = archive_entry_new()) != NULL); + archive_entry_copy_pathname(ae, "bar"); + archive_entry_set_mode(ae, S_IFREG | 0777); + archive_entry_set_size(ae, 8); + archive_entry_copy_hardlink(ae, "symlink/foo"); + assertEqualInt(ARCHIVE_FAILED, archive_write_header(a, ae)); + assertEqualInt(ARCHIVE_FAILED, archive_write_data(a, "modified", 8)); + archive_entry_free(ae); + + /* Verify that target file contents are unchanged. */ + assertTextFileContents("unmodified", "../target/foo"); +#endif +} diff --git a/contrib/libarchive/tar/cmdline.c b/contrib/libarchive/tar/cmdline.c index fd0712a0dd6c..c87741cc565e 100644 --- a/contrib/libarchive/tar/cmdline.c +++ b/contrib/libarchive/tar/cmdline.c @@ -68,6 +68,7 @@ static const struct bsdtar_option { { "auto-compress", 0, 'a' }, { "b64encode", 0, OPTION_B64ENCODE }, { "block-size", 1, 'b' }, + { "blocking-factor", 1, 'b' }, { "bunzip2", 0, 'j' }, { "bzip", 0, 'j' }, { "bzip2", 0, 'j' }, diff --git a/contrib/libarchive/tar/test/test_version.c b/contrib/libarchive/tar/test/test_version.c index 665621e19192..67771b7aa968 100644 --- a/contrib/libarchive/tar/test/test_version.c +++ b/contrib/libarchive/tar/test/test_version.c @@ -88,7 +88,7 @@ DEFINE_TEST(test_version) if (*q == 'a' || *q == 'b' || *q == 'c' || *q == 'd') ++q; /* Skip arbitrary third-party version numbers. */ - while (s > 0 && (*q == ' ' || *q == '/' || *q == '.' || isalnum(*q))) { + while (s > 0 && (*q == ' ' || *q == '-' || *q == '/' || *q == '.' || isalnum(*q))) { ++q; --s; } diff --git a/contrib/libcxxrt/libelftc_dem_gnu3.c b/contrib/libcxxrt/libelftc_dem_gnu3.c index 70ef3e8e1da8..2b38c73af55f 100644 --- a/contrib/libcxxrt/libelftc_dem_gnu3.c +++ b/contrib/libcxxrt/libelftc_dem_gnu3.c @@ -2842,7 +2842,7 @@ again: case 'w': /* wchar_t */ - if (!cpp_demangle_push_str(ddata, "wchar_t", 6)) + if (!cpp_demangle_push_str(ddata, "wchar_t", 7)) goto clean; ++ddata->cur; goto rtn; diff --git a/contrib/libdivsufsort/CHANGELOG.md b/contrib/libdivsufsort/CHANGELOG.md new file mode 100644 index 000000000000..fe9d004050dc --- /dev/null +++ b/contrib/libdivsufsort/CHANGELOG.md @@ -0,0 +1,21 @@ +# libdivsufsort Change Log + +See full changelog at: https://github.com/y-256/libdivsufsort/commits + +## [2.0.1] - 2010-11-11 +### Fixed +* Wrong variable used in `divbwt` function +* Enclose some string variables with double quotation marks in include/CMakeLists.txt +* Fix typo in include/CMakeLists.txt + +## 2.0.0 - 2008-08-23 +### Changed +* Switch the build system to [CMake](http://www.cmake.org/) +* Improve the performance of the suffix-sorting algorithm + +### Added +* OpenMP support +* 64-bit version of divsufsort + +[Unreleased]: https://github.com/y-256/libdivsufsort/compare/2.0.1...HEAD +[2.0.1]: https://github.com/y-256/libdivsufsort/compare/2.0.0...2.0.1 diff --git a/contrib/libdivsufsort/LICENSE b/contrib/libdivsufsort/LICENSE new file mode 100644 index 000000000000..249efa49a479 --- /dev/null +++ b/contrib/libdivsufsort/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2003 Yuta Mori All rights reserved. + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/contrib/libdivsufsort/README.md b/contrib/libdivsufsort/README.md new file mode 100644 index 000000000000..381a18888d58 --- /dev/null +++ b/contrib/libdivsufsort/README.md @@ -0,0 +1,140 @@ +# libdivsufsort + +libdivsufsort is a software library that implements a lightweight suffix array construction algorithm. + +## News +* 2015-03-21: The project has moved from [Google Code](http://code.google.com/p/libdivsufsort/) to [GitHub](https://github.com/y-256/libdivsufsort) + +## Introduction +This library provides a simple and an efficient C API to construct a suffix array and a Burrows-Wheeler transformed string from a given string over a constant-size alphabet. +The algorithm runs in O(n log n) worst-case time using only 5n+O(1) bytes of memory space, where n is the length of +the string. + +## Build requirements +* An ANSI C Compiler (e.g. GNU GCC) +* [CMake](http://www.cmake.org/ "CMake") version 2.4.2 or newer +* CMake-supported build tool + +## Building on GNU/Linux +1. Get the source code from GitHub. You can either + * use git to clone the repository + ``` + git clone https://github.com/y-256/libdivsufsort.git + ``` + * or download a [zip file](../../archive/master.zip) directly +2. Create a `build` directory in the package source directory. +```shell +$ cd libdivsufsort +$ mkdir build +$ cd build +``` +3. Configure the package for your system. +If you want to install to a different location, change the -DCMAKE_INSTALL_PREFIX option. +```shell +$ cmake -DCMAKE_BUILD_TYPE="Release" \ +-DCMAKE_INSTALL_PREFIX="/usr/local" .. +``` +4. Compile the package. +```shell +$ make +``` +5. (Optional) Install the library and header files. +```shell +$ sudo make install +``` + +## API +```c +/* Data types */ +typedef int32_t saint_t; +typedef int32_t saidx_t; +typedef uint8_t sauchar_t; + +/* + * Constructs the suffix array of a given string. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array or suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +saint_t +divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n); + +/* + * Constructs the burrows-wheeler transformed string of a given string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @return The primary index if no error occurred, -1 or -2 otherwise. + */ +saidx_t +divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n); +``` + +## Example Usage +```c +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <divsufsort.h> + +int main() { + // intput data + char *Text = "abracadabra"; + int n = strlen(Text); + int i, j; + + // allocate + int *SA = (int *)malloc(n * sizeof(int)); + + // sort + divsufsort((unsigned char *)Text, SA, n); + + // output + for(i = 0; i < n; ++i) { + printf("SA[%2d] = %2d: ", i, SA[i]); + for(j = SA[i]; j < n; ++j) { + printf("%c", Text[j]); + } + printf("$\n"); + } + + // deallocate + free(SA); + + return 0; +} +``` +See the [examples](examples) directory for a few other examples. + +## Benchmarks +See [Benchmarks](https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md) page for details. + +## License +libdivsufsort is released under the [MIT license](LICENSE "MIT license"). +> The MIT License (MIT) +> +> Copyright (c) 2003 Yuta Mori All rights reserved. +> +> Permission is hereby granted, free of charge, to any person obtaining a copy +> of this software and associated documentation files (the "Software"), to deal +> in the Software without restriction, including without limitation the rights +> to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +> copies of the Software, and to permit persons to whom the Software is +> furnished to do so, subject to the following conditions: +> +> The above copyright notice and this permission notice shall be included in all +> copies or substantial portions of the Software. +> +> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +> IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +> FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +> AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +> LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +> OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +> SOFTWARE. + +## Author +* Yuta Mori diff --git a/contrib/libdivsufsort/include/config.h.cmake b/contrib/libdivsufsort/include/config.h.cmake new file mode 100644 index 000000000000..6a1cf47d8a83 --- /dev/null +++ b/contrib/libdivsufsort/include/config.h.cmake @@ -0,0 +1,81 @@ +/* + * config.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _CONFIG_H +#define _CONFIG_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** Define to the version of this package. **/ +#cmakedefine PROJECT_VERSION_FULL "${PROJECT_VERSION_FULL}" + +/** Define to 1 if you have the header files. **/ +#cmakedefine HAVE_INTTYPES_H 1 +#cmakedefine HAVE_STDDEF_H 1 +#cmakedefine HAVE_STDINT_H 1 +#cmakedefine HAVE_STDLIB_H 1 +#cmakedefine HAVE_STRING_H 1 +#cmakedefine HAVE_STRINGS_H 1 +#cmakedefine HAVE_MEMORY_H 1 +#cmakedefine HAVE_SYS_TYPES_H 1 + +/** for WinIO **/ +#cmakedefine HAVE_IO_H 1 +#cmakedefine HAVE_FCNTL_H 1 +#cmakedefine HAVE__SETMODE 1 +#cmakedefine HAVE_SETMODE 1 +#cmakedefine HAVE__FILENO 1 +#cmakedefine HAVE_FOPEN_S 1 +#cmakedefine HAVE__O_BINARY 1 +#ifndef HAVE__SETMODE +# if HAVE_SETMODE +# define _setmode setmode +# define HAVE__SETMODE 1 +# endif +# if HAVE__SETMODE && !HAVE__O_BINARY +# define _O_BINARY 0 +# define HAVE__O_BINARY 1 +# endif +#endif + +/** for inline **/ +#ifndef INLINE +# define INLINE @INLINE@ +#endif + +/** for VC++ warning **/ +#ifdef _MSC_VER +#pragma warning(disable: 4127) +#endif + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _CONFIG_H */ diff --git a/contrib/libdivsufsort/include/divsufsort.h.cmake b/contrib/libdivsufsort/include/divsufsort.h.cmake new file mode 100644 index 000000000000..bcaba7c644c1 --- /dev/null +++ b/contrib/libdivsufsort/include/divsufsort.h.cmake @@ -0,0 +1,180 @@ +/* + * divsufsort@W64BIT@.h for libdivsufsort@W64BIT@ + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT@W64BIT@_H +#define _DIVSUFSORT@W64BIT@_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +@INCFILE@ + +#ifndef DIVSUFSORT_API +# ifdef DIVSUFSORT_BUILD_DLL +# define DIVSUFSORT_API @DIVSUFSORT_EXPORT@ +# else +# define DIVSUFSORT_API @DIVSUFSORT_IMPORT@ +# endif +#endif + +/*- Datatypes -*/ +#ifndef SAUCHAR_T +#define SAUCHAR_T +typedef @SAUCHAR_TYPE@ sauchar_t; +#endif /* SAUCHAR_T */ +#ifndef SAINT_T +#define SAINT_T +typedef @SAINT32_TYPE@ saint_t; +#endif /* SAINT_T */ +#ifndef SAIDX@W64BIT@_T +#define SAIDX@W64BIT@_T +typedef @SAINDEX_TYPE@ saidx@W64BIT@_t; +#endif /* SAIDX@W64BIT@_T */ +#ifndef PRIdSAINT_T +#define PRIdSAINT_T @SAINT_PRId@ +#endif /* PRIdSAINT_T */ +#ifndef PRIdSAIDX@W64BIT@_T +#define PRIdSAIDX@W64BIT@_T @SAINDEX_PRId@ +#endif /* PRIdSAIDX@W64BIT@_T */ + + +/*- Prototypes -*/ + +/** + * Constructs the suffix array of a given string. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array of suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +divsufsort@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t *SA, saidx@W64BIT@_t n); + +/** + * Constructs the burrows-wheeler transformed string of a given string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @return The primary index if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +divbwt@W64BIT@(const sauchar_t *T, sauchar_t *U, saidx@W64BIT@_t *A, saidx@W64BIT@_t n); + +/** + * Returns the version of the divsufsort library. + * @return The version number string. + */ +DIVSUFSORT_API +const char * +divsufsort@W64BIT@_version(void); + + +/** + * Constructs the burrows-wheeler transformed string of a given string and suffix array. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param SA[0..n-1] The suffix array. (can be NULL) + * @param n The length of the given string. + * @param idx The output primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +bw_transform@W64BIT@(const sauchar_t *T, sauchar_t *U, + saidx@W64BIT@_t *SA /* can NULL */, + saidx@W64BIT@_t n, saidx@W64BIT@_t *idx); + +/** + * Inverse BW-transforms a given BWTed string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @param idx The primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +inverse_bw_transform@W64BIT@(const sauchar_t *T, sauchar_t *U, + saidx@W64BIT@_t *A /* can NULL */, + saidx@W64BIT@_t n, saidx@W64BIT@_t idx); + +/** + * Checks the correctness of a given suffix array. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The input suffix array. + * @param n The length of the given string. + * @param verbose The verbose mode. + * @return 0 if no error occurred. + */ +DIVSUFSORT_API +saint_t +sufcheck@W64BIT@(const sauchar_t *T, const saidx@W64BIT@_t *SA, saidx@W64BIT@_t n, saint_t verbose); + +/** + * Search for the pattern P in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param P[0..Psize-1] The input pattern string. + * @param Psize The length of the given pattern string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +sa_search@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t Tsize, + const sauchar_t *P, saidx@W64BIT@_t Psize, + const saidx@W64BIT@_t *SA, saidx@W64BIT@_t SAsize, + saidx@W64BIT@_t *left); + +/** + * Search for the character c in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param c The input character. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx@W64BIT@_t +sa_simplesearch@W64BIT@(const sauchar_t *T, saidx@W64BIT@_t Tsize, + const saidx@W64BIT@_t *SA, saidx@W64BIT@_t SAsize, + saint_t c, saidx@W64BIT@_t *left); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT@W64BIT@_H */ diff --git a/contrib/libdivsufsort/include/divsufsort_private.h b/contrib/libdivsufsort/include/divsufsort_private.h new file mode 100644 index 000000000000..7e261c19d49e --- /dev/null +++ b/contrib/libdivsufsort/include/divsufsort_private.h @@ -0,0 +1,207 @@ +/* + * divsufsort_private.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT_PRIVATE_H +#define _DIVSUFSORT_PRIVATE_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif +#include <assert.h> +#include <stdio.h> +#if HAVE_STRING_H +# include <string.h> +#endif +#if HAVE_STDLIB_H +# include <stdlib.h> +#endif +#if HAVE_MEMORY_H +# include <memory.h> +#endif +#if HAVE_STDDEF_H +# include <stddef.h> +#endif +#if HAVE_STRINGS_H +# include <strings.h> +#endif +#if HAVE_INTTYPES_H +# include <inttypes.h> +#else +# if HAVE_STDINT_H +# include <stdint.h> +# endif +#endif +#if defined(BUILD_DIVSUFSORT64) +# include "divsufsort64.h" +# ifndef SAIDX_T +# define SAIDX_T +# define saidx_t saidx64_t +# endif /* SAIDX_T */ +# ifndef PRIdSAIDX_T +# define PRIdSAIDX_T PRIdSAIDX64_T +# endif /* PRIdSAIDX_T */ +# define divsufsort divsufsort64 +# define divbwt divbwt64 +# define divsufsort_version divsufsort64_version +# define bw_transform bw_transform64 +# define inverse_bw_transform inverse_bw_transform64 +# define sufcheck sufcheck64 +# define sa_search sa_search64 +# define sa_simplesearch sa_simplesearch64 +# define sssort sssort64 +# define trsort trsort64 +#else +# include "divsufsort.h" +#endif + + +/*- Constants -*/ +#if !defined(UINT8_MAX) +# define UINT8_MAX (255) +#endif /* UINT8_MAX */ +#if defined(ALPHABET_SIZE) && (ALPHABET_SIZE < 1) +# undef ALPHABET_SIZE +#endif +#if !defined(ALPHABET_SIZE) +# define ALPHABET_SIZE (UINT8_MAX + 1) +#endif +/* for divsufsort.c */ +#define BUCKET_A_SIZE (ALPHABET_SIZE) +#define BUCKET_B_SIZE (ALPHABET_SIZE * ALPHABET_SIZE) +/* for sssort.c */ +#if defined(SS_INSERTIONSORT_THRESHOLD) +# if SS_INSERTIONSORT_THRESHOLD < 1 +# undef SS_INSERTIONSORT_THRESHOLD +# define SS_INSERTIONSORT_THRESHOLD (1) +# endif +#else +# define SS_INSERTIONSORT_THRESHOLD (8) +#endif +#if defined(SS_BLOCKSIZE) +# if SS_BLOCKSIZE < 0 +# undef SS_BLOCKSIZE +# define SS_BLOCKSIZE (0) +# elif 32768 <= SS_BLOCKSIZE +# undef SS_BLOCKSIZE +# define SS_BLOCKSIZE (32767) +# endif +#else +# define SS_BLOCKSIZE (1024) +#endif +/* minstacksize = log(SS_BLOCKSIZE) / log(3) * 2 */ +#if SS_BLOCKSIZE == 0 +# if defined(BUILD_DIVSUFSORT64) +# define SS_MISORT_STACKSIZE (96) +# else +# define SS_MISORT_STACKSIZE (64) +# endif +#elif SS_BLOCKSIZE <= 4096 +# define SS_MISORT_STACKSIZE (16) +#else +# define SS_MISORT_STACKSIZE (24) +#endif +#if defined(BUILD_DIVSUFSORT64) +# define SS_SMERGE_STACKSIZE (64) +#else +# define SS_SMERGE_STACKSIZE (32) +#endif +/* for trsort.c */ +#define TR_INSERTIONSORT_THRESHOLD (8) +#if defined(BUILD_DIVSUFSORT64) +# define TR_STACKSIZE (96) +#else +# define TR_STACKSIZE (64) +#endif + + +/*- Macros -*/ +#ifndef SWAP +# define SWAP(_a, _b) do { t = (_a); (_a) = (_b); (_b) = t; } while(0) +#endif /* SWAP */ +#ifndef MIN +# define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b)) +#endif /* MIN */ +#ifndef MAX +# define MAX(_a, _b) (((_a) > (_b)) ? (_a) : (_b)) +#endif /* MAX */ +#define STACK_PUSH(_a, _b, _c, _d)\ + do {\ + assert(ssize < STACK_SIZE);\ + stack[ssize].a = (_a), stack[ssize].b = (_b),\ + stack[ssize].c = (_c), stack[ssize++].d = (_d);\ + } while(0) +#define STACK_PUSH5(_a, _b, _c, _d, _e)\ + do {\ + assert(ssize < STACK_SIZE);\ + stack[ssize].a = (_a), stack[ssize].b = (_b),\ + stack[ssize].c = (_c), stack[ssize].d = (_d), stack[ssize++].e = (_e);\ + } while(0) +#define STACK_POP(_a, _b, _c, _d)\ + do {\ + assert(0 <= ssize);\ + if(ssize == 0) { return; }\ + (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ + (_c) = stack[ssize].c, (_d) = stack[ssize].d;\ + } while(0) +#define STACK_POP5(_a, _b, _c, _d, _e)\ + do {\ + assert(0 <= ssize);\ + if(ssize == 0) { return; }\ + (_a) = stack[--ssize].a, (_b) = stack[ssize].b,\ + (_c) = stack[ssize].c, (_d) = stack[ssize].d, (_e) = stack[ssize].e;\ + } while(0) +/* for divsufsort.c */ +#define BUCKET_A(_c0) bucket_A[(_c0)] +#if ALPHABET_SIZE == 256 +#define BUCKET_B(_c0, _c1) (bucket_B[((_c1) << 8) | (_c0)]) +#define BUCKET_BSTAR(_c0, _c1) (bucket_B[((_c0) << 8) | (_c1)]) +#else +#define BUCKET_B(_c0, _c1) (bucket_B[(_c1) * ALPHABET_SIZE + (_c0)]) +#define BUCKET_BSTAR(_c0, _c1) (bucket_B[(_c0) * ALPHABET_SIZE + (_c1)]) +#endif + + +/*- Private Prototypes -*/ +/* sssort.c */ +void +sssort(const sauchar_t *Td, const saidx_t *PA, + saidx_t *first, saidx_t *last, + saidx_t *buf, saidx_t bufsize, + saidx_t depth, saidx_t n, saint_t lastsuffix); +/* trsort.c */ +void +trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT_PRIVATE_H */ diff --git a/contrib/libdivsufsort/lib/divsufsort.c b/contrib/libdivsufsort/lib/divsufsort.c new file mode 100644 index 000000000000..9f64b4f48adb --- /dev/null +++ b/contrib/libdivsufsort/lib/divsufsort.c @@ -0,0 +1,398 @@ +/* + * divsufsort.c for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#include "divsufsort_private.h" +#ifdef _OPENMP +# include <omp.h> +#endif + + +/*- Private Functions -*/ + +/* Sorts suffixes of type B*. */ +static +saidx_t +sort_typeBstar(const sauchar_t *T, saidx_t *SA, + saidx_t *bucket_A, saidx_t *bucket_B, + saidx_t n) { + saidx_t *PAb, *ISAb, *buf; +#ifdef _OPENMP + saidx_t *curbuf; + saidx_t l; +#endif + saidx_t i, j, k, t, m, bufsize; + saint_t c0, c1; +#ifdef _OPENMP + saint_t d0, d1; + int tmp; +#endif + + /* Initialize bucket arrays. */ + for(i = 0; i < BUCKET_A_SIZE; ++i) { bucket_A[i] = 0; } + for(i = 0; i < BUCKET_B_SIZE; ++i) { bucket_B[i] = 0; } + + /* Count the number of occurrences of the first one or two characters of each + type A, B and B* suffix. Moreover, store the beginning position of all + type B* suffixes into the array SA. */ + for(i = n - 1, m = n, c0 = T[n - 1]; 0 <= i;) { + /* type A suffix. */ + do { ++BUCKET_A(c1 = c0); } while((0 <= --i) && ((c0 = T[i]) >= c1)); + if(0 <= i) { + /* type B* suffix. */ + ++BUCKET_BSTAR(c0, c1); + SA[--m] = i; + /* type B suffix. */ + for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { + ++BUCKET_B(c0, c1); + } + } + } + m = n - m; +/* +note: + A type B* suffix is lexicographically smaller than a type B suffix that + begins with the same first two characters. +*/ + + /* Calculate the index of start/end point of each bucket. */ + for(c0 = 0, i = 0, j = 0; c0 < ALPHABET_SIZE; ++c0) { + t = i + BUCKET_A(c0); + BUCKET_A(c0) = i + j; /* start point */ + i = t + BUCKET_B(c0, c0); + for(c1 = c0 + 1; c1 < ALPHABET_SIZE; ++c1) { + j += BUCKET_BSTAR(c0, c1); + BUCKET_BSTAR(c0, c1) = j; /* end point */ + i += BUCKET_B(c0, c1); + } + } + + if(0 < m) { + /* Sort the type B* suffixes by their first two characters. */ + PAb = SA + n - m; ISAb = SA + m; + for(i = m - 2; 0 <= i; --i) { + t = PAb[i], c0 = T[t], c1 = T[t + 1]; + SA[--BUCKET_BSTAR(c0, c1)] = i; + } + t = PAb[m - 1], c0 = T[t], c1 = T[t + 1]; + SA[--BUCKET_BSTAR(c0, c1)] = m - 1; + + /* Sort the type B* substrings using sssort. */ +#ifdef _OPENMP + tmp = omp_get_max_threads(); + buf = SA + m, bufsize = (n - (2 * m)) / tmp; + c0 = ALPHABET_SIZE - 2, c1 = ALPHABET_SIZE - 1, j = m; +#pragma omp parallel default(shared) private(curbuf, k, l, d0, d1, tmp) + { + tmp = omp_get_thread_num(); + curbuf = buf + tmp * bufsize; + k = 0; + for(;;) { + #pragma omp critical(sssort_lock) + { + if(0 < (l = j)) { + d0 = c0, d1 = c1; + do { + k = BUCKET_BSTAR(d0, d1); + if(--d1 <= d0) { + d1 = ALPHABET_SIZE - 1; + if(--d0 < 0) { break; } + } + } while(((l - k) <= 1) && (0 < (l = k))); + c0 = d0, c1 = d1, j = k; + } + } + if(l == 0) { break; } + sssort(T, PAb, SA + k, SA + l, + curbuf, bufsize, 2, n, *(SA + k) == (m - 1)); + } + } +#else + buf = SA + m, bufsize = n - (2 * m); + for(c0 = ALPHABET_SIZE - 2, j = m; 0 < j; --c0) { + for(c1 = ALPHABET_SIZE - 1; c0 < c1; j = i, --c1) { + i = BUCKET_BSTAR(c0, c1); + if(1 < (j - i)) { + sssort(T, PAb, SA + i, SA + j, + buf, bufsize, 2, n, *(SA + i) == (m - 1)); + } + } + } +#endif + + /* Compute ranks of type B* substrings. */ + for(i = m - 1; 0 <= i; --i) { + if(0 <= SA[i]) { + j = i; + do { ISAb[SA[i]] = i; } while((0 <= --i) && (0 <= SA[i])); + SA[i + 1] = i - j; + if(i <= 0) { break; } + } + j = i; + do { ISAb[SA[i] = ~SA[i]] = j; } while(SA[--i] < 0); + ISAb[SA[i]] = j; + } + + /* Construct the inverse suffix array of type B* suffixes using trsort. */ + trsort(ISAb, SA, m, 1); + + /* Set the sorted order of tyoe B* suffixes. */ + for(i = n - 1, j = m, c0 = T[n - 1]; 0 <= i;) { + for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) >= c1); --i, c1 = c0) { } + if(0 <= i) { + t = i; + for(--i, c1 = c0; (0 <= i) && ((c0 = T[i]) <= c1); --i, c1 = c0) { } + SA[ISAb[--j]] = ((t == 0) || (1 < (t - i))) ? t : ~t; + } + } + + /* Calculate the index of start/end point of each bucket. */ + BUCKET_B(ALPHABET_SIZE - 1, ALPHABET_SIZE - 1) = n; /* end point */ + for(c0 = ALPHABET_SIZE - 2, k = m - 1; 0 <= c0; --c0) { + i = BUCKET_A(c0 + 1) - 1; + for(c1 = ALPHABET_SIZE - 1; c0 < c1; --c1) { + t = i - BUCKET_B(c0, c1); + BUCKET_B(c0, c1) = i; /* end point */ + + /* Move all type B* suffixes to the correct position. */ + for(i = t, j = BUCKET_BSTAR(c0, c1); + j <= k; + --i, --k) { SA[i] = SA[k]; } + } + BUCKET_BSTAR(c0, c0 + 1) = i - BUCKET_B(c0, c0) + 1; /* start point */ + BUCKET_B(c0, c0) = i; /* end point */ + } + } + + return m; +} + +/* Constructs the suffix array by using the sorted order of type B* suffixes. */ +static +void +construct_SA(const sauchar_t *T, saidx_t *SA, + saidx_t *bucket_A, saidx_t *bucket_B, + saidx_t n, saidx_t m) { + saidx_t *i, *j, *k; + saidx_t s; + saint_t c0, c1, c2; + + if(0 < m) { + /* Construct the sorted order of type B suffixes by using + the sorted order of type B* suffixes. */ + for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) { + /* Scan the suffix array from right to left. */ + for(i = SA + BUCKET_BSTAR(c1, c1 + 1), + j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; + i <= j; + --j) { + if(0 < (s = *j)) { + assert(T[s] == c1); + assert(((s + 1) < n) && (T[s] <= T[s + 1])); + assert(T[s - 1] <= T[s]); + *j = ~s; + c0 = T[--s]; + if((0 < s) && (T[s - 1] > c0)) { s = ~s; } + if(c0 != c2) { + if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } + k = SA + BUCKET_B(c2 = c0, c1); + } + assert(k < j); + *k-- = s; + } else { + assert(((s == 0) && (T[s] == c1)) || (s < 0)); + *j = ~s; + } + } + } + } + + /* Construct the suffix array by using + the sorted order of type B suffixes. */ + k = SA + BUCKET_A(c2 = T[n - 1]); + *k++ = (T[n - 2] < c2) ? ~(n - 1) : (n - 1); + /* Scan the suffix array from left to right. */ + for(i = SA, j = SA + n; i < j; ++i) { + if(0 < (s = *i)) { + assert(T[s - 1] >= T[s]); + c0 = T[--s]; + if((s == 0) || (T[s - 1] < c0)) { s = ~s; } + if(c0 != c2) { + BUCKET_A(c2) = k - SA; + k = SA + BUCKET_A(c2 = c0); + } + assert(i < k); + *k++ = s; + } else { + assert(s < 0); + *i = ~s; + } + } +} + +/* Constructs the burrows-wheeler transformed string directly + by using the sorted order of type B* suffixes. */ +static +saidx_t +construct_BWT(const sauchar_t *T, saidx_t *SA, + saidx_t *bucket_A, saidx_t *bucket_B, + saidx_t n, saidx_t m) { + saidx_t *i, *j, *k, *orig; + saidx_t s; + saint_t c0, c1, c2; + + if(0 < m) { + /* Construct the sorted order of type B suffixes by using + the sorted order of type B* suffixes. */ + for(c1 = ALPHABET_SIZE - 2; 0 <= c1; --c1) { + /* Scan the suffix array from right to left. */ + for(i = SA + BUCKET_BSTAR(c1, c1 + 1), + j = SA + BUCKET_A(c1 + 1) - 1, k = NULL, c2 = -1; + i <= j; + --j) { + if(0 < (s = *j)) { + assert(T[s] == c1); + assert(((s + 1) < n) && (T[s] <= T[s + 1])); + assert(T[s - 1] <= T[s]); + c0 = T[--s]; + *j = ~((saidx_t)c0); + if((0 < s) && (T[s - 1] > c0)) { s = ~s; } + if(c0 != c2) { + if(0 <= c2) { BUCKET_B(c2, c1) = k - SA; } + k = SA + BUCKET_B(c2 = c0, c1); + } + assert(k < j); + *k-- = s; + } else if(s != 0) { + *j = ~s; +#ifndef NDEBUG + } else { + assert(T[s] == c1); +#endif + } + } + } + } + + /* Construct the BWTed string by using + the sorted order of type B suffixes. */ + k = SA + BUCKET_A(c2 = T[n - 1]); + *k++ = (T[n - 2] < c2) ? ~((saidx_t)T[n - 2]) : (n - 1); + /* Scan the suffix array from left to right. */ + for(i = SA, j = SA + n, orig = SA; i < j; ++i) { + if(0 < (s = *i)) { + assert(T[s - 1] >= T[s]); + c0 = T[--s]; + *i = c0; + if((0 < s) && (T[s - 1] < c0)) { s = ~((saidx_t)T[s - 1]); } + if(c0 != c2) { + BUCKET_A(c2) = k - SA; + k = SA + BUCKET_A(c2 = c0); + } + assert(i < k); + *k++ = s; + } else if(s != 0) { + *i = ~s; + } else { + orig = i; + } + } + + return orig - SA; +} + + +/*---------------------------------------------------------------------------*/ + +/*- Function -*/ + +saint_t +divsufsort(const sauchar_t *T, saidx_t *SA, saidx_t n) { + saidx_t *bucket_A, *bucket_B; + saidx_t m; + saint_t err = 0; + + /* Check arguments. */ + if((T == NULL) || (SA == NULL) || (n < 0)) { return -1; } + else if(n == 0) { return 0; } + else if(n == 1) { SA[0] = 0; return 0; } + else if(n == 2) { m = (T[0] < T[1]); SA[m ^ 1] = 0, SA[m] = 1; return 0; } + + bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t)); + bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t)); + + /* Suffixsort. */ + if((bucket_A != NULL) && (bucket_B != NULL)) { + m = sort_typeBstar(T, SA, bucket_A, bucket_B, n); + construct_SA(T, SA, bucket_A, bucket_B, n, m); + } else { + err = -2; + } + + free(bucket_B); + free(bucket_A); + + return err; +} + +saidx_t +divbwt(const sauchar_t *T, sauchar_t *U, saidx_t *A, saidx_t n) { + saidx_t *B; + saidx_t *bucket_A, *bucket_B; + saidx_t m, pidx, i; + + /* Check arguments. */ + if((T == NULL) || (U == NULL) || (n < 0)) { return -1; } + else if(n <= 1) { if(n == 1) { U[0] = T[0]; } return n; } + + if((B = A) == NULL) { B = (saidx_t *)malloc((size_t)(n + 1) * sizeof(saidx_t)); } + bucket_A = (saidx_t *)malloc(BUCKET_A_SIZE * sizeof(saidx_t)); + bucket_B = (saidx_t *)malloc(BUCKET_B_SIZE * sizeof(saidx_t)); + + /* Burrows-Wheeler Transform. */ + if((B != NULL) && (bucket_A != NULL) && (bucket_B != NULL)) { + m = sort_typeBstar(T, B, bucket_A, bucket_B, n); + pidx = construct_BWT(T, B, bucket_A, bucket_B, n, m); + + /* Copy to output string. */ + U[0] = T[n - 1]; + for(i = 0; i < pidx; ++i) { U[i + 1] = (sauchar_t)B[i]; } + for(i += 1; i < n; ++i) { U[i] = (sauchar_t)B[i]; } + pidx += 1; + } else { + pidx = -2; + } + + free(bucket_B); + free(bucket_A); + if(A == NULL) { free(B); } + + return pidx; +} + +const char * +divsufsort_version(void) { + return PROJECT_VERSION_FULL; +} diff --git a/contrib/libdivsufsort/lib/sssort.c b/contrib/libdivsufsort/lib/sssort.c new file mode 100644 index 000000000000..4a18fd2ab495 --- /dev/null +++ b/contrib/libdivsufsort/lib/sssort.c @@ -0,0 +1,815 @@ +/* + * sssort.c for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#include "divsufsort_private.h" + + +/*- Private Functions -*/ + +static const saint_t lg_table[256]= { + -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 +}; + +#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) + +static INLINE +saint_t +ss_ilg(saidx_t n) { +#if SS_BLOCKSIZE == 0 +# if defined(BUILD_DIVSUFSORT64) + return (n >> 32) ? + ((n >> 48) ? + ((n >> 56) ? + 56 + lg_table[(n >> 56) & 0xff] : + 48 + lg_table[(n >> 48) & 0xff]) : + ((n >> 40) ? + 40 + lg_table[(n >> 40) & 0xff] : + 32 + lg_table[(n >> 32) & 0xff])) : + ((n & 0xffff0000) ? + ((n & 0xff000000) ? + 24 + lg_table[(n >> 24) & 0xff] : + 16 + lg_table[(n >> 16) & 0xff]) : + ((n & 0x0000ff00) ? + 8 + lg_table[(n >> 8) & 0xff] : + 0 + lg_table[(n >> 0) & 0xff])); +# else + return (n & 0xffff0000) ? + ((n & 0xff000000) ? + 24 + lg_table[(n >> 24) & 0xff] : + 16 + lg_table[(n >> 16) & 0xff]) : + ((n & 0x0000ff00) ? + 8 + lg_table[(n >> 8) & 0xff] : + 0 + lg_table[(n >> 0) & 0xff]); +# endif +#elif SS_BLOCKSIZE < 256 + return lg_table[n]; +#else + return (n & 0xff00) ? + 8 + lg_table[(n >> 8) & 0xff] : + 0 + lg_table[(n >> 0) & 0xff]; +#endif +} + +#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */ + +#if SS_BLOCKSIZE != 0 + +static const saint_t sqq_table[256] = { + 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61, + 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89, + 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109, +110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, +128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, +143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, +156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168, +169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, +181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191, +192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201, +202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211, +212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, +221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, +230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238, +239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, +247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 +}; + +static INLINE +saidx_t +ss_isqrt(saidx_t x) { + saidx_t y, e; + + if(x >= (SS_BLOCKSIZE * SS_BLOCKSIZE)) { return SS_BLOCKSIZE; } + e = (x & 0xffff0000) ? + ((x & 0xff000000) ? + 24 + lg_table[(x >> 24) & 0xff] : + 16 + lg_table[(x >> 16) & 0xff]) : + ((x & 0x0000ff00) ? + 8 + lg_table[(x >> 8) & 0xff] : + 0 + lg_table[(x >> 0) & 0xff]); + + if(e >= 16) { + y = sqq_table[x >> ((e - 6) - (e & 1))] << ((e >> 1) - 7); + if(e >= 24) { y = (y + 1 + x / y) >> 1; } + y = (y + 1 + x / y) >> 1; + } else if(e >= 8) { + y = (sqq_table[x >> ((e - 6) - (e & 1))] >> (7 - (e >> 1))) + 1; + } else { + return sqq_table[x] >> 4; + } + + return (x < (y * y)) ? y - 1 : y; +} + +#endif /* SS_BLOCKSIZE != 0 */ + + +/*---------------------------------------------------------------------------*/ + +/* Compares two suffixes. */ +static INLINE +saint_t +ss_compare(const sauchar_t *T, + const saidx_t *p1, const saidx_t *p2, + saidx_t depth) { + const sauchar_t *U1, *U2, *U1n, *U2n; + + for(U1 = T + depth + *p1, + U2 = T + depth + *p2, + U1n = T + *(p1 + 1) + 2, + U2n = T + *(p2 + 1) + 2; + (U1 < U1n) && (U2 < U2n) && (*U1 == *U2); + ++U1, ++U2) { + } + + return U1 < U1n ? + (U2 < U2n ? *U1 - *U2 : 1) : + (U2 < U2n ? -1 : 0); +} + + +/*---------------------------------------------------------------------------*/ + +#if (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) + +/* Insertionsort for small size groups */ +static +void +ss_insertionsort(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *last, saidx_t depth) { + saidx_t *i, *j; + saidx_t t; + saint_t r; + + for(i = last - 2; first <= i; --i) { + for(t = *i, j = i + 1; 0 < (r = ss_compare(T, PA + t, PA + *j, depth));) { + do { *(j - 1) = *j; } while((++j < last) && (*j < 0)); + if(last <= j) { break; } + } + if(r == 0) { *j = ~*j; } + *(j - 1) = t; + } +} + +#endif /* (SS_BLOCKSIZE != 1) && (SS_INSERTIONSORT_THRESHOLD != 1) */ + + +/*---------------------------------------------------------------------------*/ + +#if (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) + +static INLINE +void +ss_fixdown(const sauchar_t *Td, const saidx_t *PA, + saidx_t *SA, saidx_t i, saidx_t size) { + saidx_t j, k; + saidx_t v; + saint_t c, d, e; + + for(v = SA[i], c = Td[PA[v]]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { + d = Td[PA[SA[k = j++]]]; + if(d < (e = Td[PA[SA[j]]])) { k = j; d = e; } + if(d <= c) { break; } + } + SA[i] = v; +} + +/* Simple top-down heapsort. */ +static +void +ss_heapsort(const sauchar_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size) { + saidx_t i, m; + saidx_t t; + + m = size; + if((size % 2) == 0) { + m--; + if(Td[PA[SA[m / 2]]] < Td[PA[SA[m]]]) { SWAP(SA[m], SA[m / 2]); } + } + + for(i = m / 2 - 1; 0 <= i; --i) { ss_fixdown(Td, PA, SA, i, m); } + if((size % 2) == 0) { SWAP(SA[0], SA[m]); ss_fixdown(Td, PA, SA, 0, m); } + for(i = m - 1; 0 < i; --i) { + t = SA[0], SA[0] = SA[i]; + ss_fixdown(Td, PA, SA, 0, i); + SA[i] = t; + } +} + + +/*---------------------------------------------------------------------------*/ + +/* Returns the median of three elements. */ +static INLINE +saidx_t * +ss_median3(const sauchar_t *Td, const saidx_t *PA, + saidx_t *v1, saidx_t *v2, saidx_t *v3) { + saidx_t *t; + if(Td[PA[*v1]] > Td[PA[*v2]]) { SWAP(v1, v2); } + if(Td[PA[*v2]] > Td[PA[*v3]]) { + if(Td[PA[*v1]] > Td[PA[*v3]]) { return v1; } + else { return v3; } + } + return v2; +} + +/* Returns the median of five elements. */ +static INLINE +saidx_t * +ss_median5(const sauchar_t *Td, const saidx_t *PA, + saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5) { + saidx_t *t; + if(Td[PA[*v2]] > Td[PA[*v3]]) { SWAP(v2, v3); } + if(Td[PA[*v4]] > Td[PA[*v5]]) { SWAP(v4, v5); } + if(Td[PA[*v2]] > Td[PA[*v4]]) { SWAP(v2, v4); SWAP(v3, v5); } + if(Td[PA[*v1]] > Td[PA[*v3]]) { SWAP(v1, v3); } + if(Td[PA[*v1]] > Td[PA[*v4]]) { SWAP(v1, v4); SWAP(v3, v5); } + if(Td[PA[*v3]] > Td[PA[*v4]]) { return v4; } + return v3; +} + +/* Returns the pivot element. */ +static INLINE +saidx_t * +ss_pivot(const sauchar_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last) { + saidx_t *middle; + saidx_t t; + + t = last - first; + middle = first + t / 2; + + if(t <= 512) { + if(t <= 32) { + return ss_median3(Td, PA, first, middle, last - 1); + } else { + t >>= 2; + return ss_median5(Td, PA, first, first + t, middle, last - 1 - t, last - 1); + } + } + t >>= 3; + first = ss_median3(Td, PA, first, first + t, first + (t << 1)); + middle = ss_median3(Td, PA, middle - t, middle, middle + t); + last = ss_median3(Td, PA, last - 1 - (t << 1), last - 1 - t, last - 1); + return ss_median3(Td, PA, first, middle, last); +} + + +/*---------------------------------------------------------------------------*/ + +/* Binary partition for substrings. */ +static INLINE +saidx_t * +ss_partition(const saidx_t *PA, + saidx_t *first, saidx_t *last, saidx_t depth) { + saidx_t *a, *b; + saidx_t t; + for(a = first - 1, b = last;;) { + for(; (++a < b) && ((PA[*a] + depth) >= (PA[*a + 1] + 1));) { *a = ~*a; } + for(; (a < --b) && ((PA[*b] + depth) < (PA[*b + 1] + 1));) { } + if(b <= a) { break; } + t = ~*b; + *b = *a; + *a = t; + } + if(first < a) { *first = ~*first; } + return a; +} + +/* Multikey introsort for medium size groups. */ +static +void +ss_mintrosort(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *last, + saidx_t depth) { +#define STACK_SIZE SS_MISORT_STACKSIZE + struct { saidx_t *a, *b, c; saint_t d; } stack[STACK_SIZE]; + const sauchar_t *Td; + saidx_t *a, *b, *c, *d, *e, *f; + saidx_t s, t; + saint_t ssize; + saint_t limit; + saint_t v, x = 0; + + for(ssize = 0, limit = ss_ilg(last - first);;) { + + if((last - first) <= SS_INSERTIONSORT_THRESHOLD) { +#if 1 < SS_INSERTIONSORT_THRESHOLD + if(1 < (last - first)) { ss_insertionsort(T, PA, first, last, depth); } +#endif + STACK_POP(first, last, depth, limit); + continue; + } + + Td = T + depth; + if(limit-- == 0) { ss_heapsort(Td, PA, first, last - first); } + if(limit < 0) { + for(a = first + 1, v = Td[PA[*first]]; a < last; ++a) { + if((x = Td[PA[*a]]) != v) { + if(1 < (a - first)) { break; } + v = x; + first = a; + } + } + if(Td[PA[*first] - 1] < v) { + first = ss_partition(PA, first, a, depth); + } + if((a - first) <= (last - a)) { + if(1 < (a - first)) { + STACK_PUSH(a, last, depth, -1); + last = a, depth += 1, limit = ss_ilg(a - first); + } else { + first = a, limit = -1; + } + } else { + if(1 < (last - a)) { + STACK_PUSH(first, a, depth + 1, ss_ilg(a - first)); + first = a, limit = -1; + } else { + last = a, depth += 1, limit = ss_ilg(a - first); + } + } + continue; + } + + /* choose pivot */ + a = ss_pivot(Td, PA, first, last); + v = Td[PA[*a]]; + SWAP(*first, *a); + + /* partition */ + for(b = first; (++b < last) && ((x = Td[PA[*b]]) == v);) { } + if(((a = b) < last) && (x < v)) { + for(; (++b < last) && ((x = Td[PA[*b]]) <= v);) { + if(x == v) { SWAP(*b, *a); ++a; } + } + } + for(c = last; (b < --c) && ((x = Td[PA[*c]]) == v);) { } + if((b < (d = c)) && (x > v)) { + for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { + if(x == v) { SWAP(*c, *d); --d; } + } + } + for(; b < c;) { + SWAP(*b, *c); + for(; (++b < c) && ((x = Td[PA[*b]]) <= v);) { + if(x == v) { SWAP(*b, *a); ++a; } + } + for(; (b < --c) && ((x = Td[PA[*c]]) >= v);) { + if(x == v) { SWAP(*c, *d); --d; } + } + } + + if(a <= d) { + c = b - 1; + + if((s = a - first) > (t = b - a)) { s = t; } + for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } + if((s = d - c) > (t = last - d - 1)) { s = t; } + for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } + + a = first + (b - a), c = last - (d - c); + b = (v <= Td[PA[*a] - 1]) ? a : ss_partition(PA, a, c, depth); + + if((a - first) <= (last - c)) { + if((last - c) <= (c - b)) { + STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); + STACK_PUSH(c, last, depth, limit); + last = a; + } else if((a - first) <= (c - b)) { + STACK_PUSH(c, last, depth, limit); + STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); + last = a; + } else { + STACK_PUSH(c, last, depth, limit); + STACK_PUSH(first, a, depth, limit); + first = b, last = c, depth += 1, limit = ss_ilg(c - b); + } + } else { + if((a - first) <= (c - b)) { + STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); + STACK_PUSH(first, a, depth, limit); + first = c; + } else if((last - c) <= (c - b)) { + STACK_PUSH(first, a, depth, limit); + STACK_PUSH(b, c, depth + 1, ss_ilg(c - b)); + first = c; + } else { + STACK_PUSH(first, a, depth, limit); + STACK_PUSH(c, last, depth, limit); + first = b, last = c, depth += 1, limit = ss_ilg(c - b); + } + } + } else { + limit += 1; + if(Td[PA[*first] - 1] < v) { + first = ss_partition(PA, first, last, depth); + limit = ss_ilg(last - first); + } + depth += 1; + } + } +#undef STACK_SIZE +} + +#endif /* (SS_BLOCKSIZE == 0) || (SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE) */ + + +/*---------------------------------------------------------------------------*/ + +#if SS_BLOCKSIZE != 0 + +static INLINE +void +ss_blockswap(saidx_t *a, saidx_t *b, saidx_t n) { + saidx_t t; + for(; 0 < n; --n, ++a, ++b) { + t = *a, *a = *b, *b = t; + } +} + +static INLINE +void +ss_rotate(saidx_t *first, saidx_t *middle, saidx_t *last) { + saidx_t *a, *b, t; + saidx_t l, r; + l = middle - first, r = last - middle; + for(; (0 < l) && (0 < r);) { + if(l == r) { ss_blockswap(first, middle, l); break; } + if(l < r) { + a = last - 1, b = middle - 1; + t = *a; + do { + *a-- = *b, *b-- = *a; + if(b < first) { + *a = t; + last = a; + if((r -= l + 1) <= l) { break; } + a -= 1, b = middle - 1; + t = *a; + } + } while(1); + } else { + a = first, b = middle; + t = *a; + do { + *a++ = *b, *b++ = *a; + if(last <= b) { + *a = t; + first = a + 1; + if((l -= r + 1) <= r) { break; } + a += 1, b = middle; + t = *a; + } + } while(1); + } + } +} + + +/*---------------------------------------------------------------------------*/ + +static +void +ss_inplacemerge(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *middle, saidx_t *last, + saidx_t depth) { + const saidx_t *p; + saidx_t *a, *b; + saidx_t len, half; + saint_t q, r; + saint_t x; + + for(;;) { + if(*(last - 1) < 0) { x = 1; p = PA + ~*(last - 1); } + else { x = 0; p = PA + *(last - 1); } + for(a = first, len = middle - first, half = len >> 1, r = -1; + 0 < len; + len = half, half >>= 1) { + b = a + half; + q = ss_compare(T, PA + ((0 <= *b) ? *b : ~*b), p, depth); + if(q < 0) { + a = b + 1; + half -= (len & 1) ^ 1; + } else { + r = q; + } + } + if(a < middle) { + if(r == 0) { *a = ~*a; } + ss_rotate(a, middle, last); + last -= middle - a; + middle = a; + if(first == middle) { break; } + } + --last; + if(x != 0) { while(*--last < 0) { } } + if(middle == last) { break; } + } +} + + +/*---------------------------------------------------------------------------*/ + +/* Merge-forward with internal buffer. */ +static +void +ss_mergeforward(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *middle, saidx_t *last, + saidx_t *buf, saidx_t depth) { + saidx_t *a, *b, *c, *bufend; + saidx_t t; + saint_t r; + + bufend = buf + (middle - first) - 1; + ss_blockswap(buf, first, middle - first); + + for(t = *(a = first), b = buf, c = middle;;) { + r = ss_compare(T, PA + *b, PA + *c, depth); + if(r < 0) { + do { + *a++ = *b; + if(bufend <= b) { *bufend = t; return; } + *b++ = *a; + } while(*b < 0); + } else if(r > 0) { + do { + *a++ = *c, *c++ = *a; + if(last <= c) { + while(b < bufend) { *a++ = *b, *b++ = *a; } + *a = *b, *b = t; + return; + } + } while(*c < 0); + } else { + *c = ~*c; + do { + *a++ = *b; + if(bufend <= b) { *bufend = t; return; } + *b++ = *a; + } while(*b < 0); + + do { + *a++ = *c, *c++ = *a; + if(last <= c) { + while(b < bufend) { *a++ = *b, *b++ = *a; } + *a = *b, *b = t; + return; + } + } while(*c < 0); + } + } +} + +/* Merge-backward with internal buffer. */ +static +void +ss_mergebackward(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *middle, saidx_t *last, + saidx_t *buf, saidx_t depth) { + const saidx_t *p1, *p2; + saidx_t *a, *b, *c, *bufend; + saidx_t t; + saint_t r; + saint_t x; + + bufend = buf + (last - middle) - 1; + ss_blockswap(buf, middle, last - middle); + + x = 0; + if(*bufend < 0) { p1 = PA + ~*bufend; x |= 1; } + else { p1 = PA + *bufend; } + if(*(middle - 1) < 0) { p2 = PA + ~*(middle - 1); x |= 2; } + else { p2 = PA + *(middle - 1); } + for(t = *(a = last - 1), b = bufend, c = middle - 1;;) { + r = ss_compare(T, p1, p2, depth); + if(0 < r) { + if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } + *a-- = *b; + if(b <= buf) { *buf = t; break; } + *b-- = *a; + if(*b < 0) { p1 = PA + ~*b; x |= 1; } + else { p1 = PA + *b; } + } else if(r < 0) { + if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } + *a-- = *c, *c-- = *a; + if(c < first) { + while(buf < b) { *a-- = *b, *b-- = *a; } + *a = *b, *b = t; + break; + } + if(*c < 0) { p2 = PA + ~*c; x |= 2; } + else { p2 = PA + *c; } + } else { + if(x & 1) { do { *a-- = *b, *b-- = *a; } while(*b < 0); x ^= 1; } + *a-- = ~*b; + if(b <= buf) { *buf = t; break; } + *b-- = *a; + if(x & 2) { do { *a-- = *c, *c-- = *a; } while(*c < 0); x ^= 2; } + *a-- = *c, *c-- = *a; + if(c < first) { + while(buf < b) { *a-- = *b, *b-- = *a; } + *a = *b, *b = t; + break; + } + if(*b < 0) { p1 = PA + ~*b; x |= 1; } + else { p1 = PA + *b; } + if(*c < 0) { p2 = PA + ~*c; x |= 2; } + else { p2 = PA + *c; } + } + } +} + +/* D&C based merge. */ +static +void +ss_swapmerge(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *middle, saidx_t *last, + saidx_t *buf, saidx_t bufsize, saidx_t depth) { +#define STACK_SIZE SS_SMERGE_STACKSIZE +#define GETIDX(a) ((0 <= (a)) ? (a) : (~(a))) +#define MERGE_CHECK(a, b, c)\ + do {\ + if(((c) & 1) ||\ + (((c) & 2) && (ss_compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0))) {\ + *(a) = ~*(a);\ + }\ + if(((c) & 4) && ((ss_compare(T, PA + GETIDX(*((b) - 1)), PA + *(b), depth) == 0))) {\ + *(b) = ~*(b);\ + }\ + } while(0) + struct { saidx_t *a, *b, *c; saint_t d; } stack[STACK_SIZE]; + saidx_t *l, *r, *lm, *rm; + saidx_t m, len, half; + saint_t ssize; + saint_t check, next; + + for(check = 0, ssize = 0;;) { + if((last - middle) <= bufsize) { + if((first < middle) && (middle < last)) { + ss_mergebackward(T, PA, first, middle, last, buf, depth); + } + MERGE_CHECK(first, last, check); + STACK_POP(first, middle, last, check); + continue; + } + + if((middle - first) <= bufsize) { + if(first < middle) { + ss_mergeforward(T, PA, first, middle, last, buf, depth); + } + MERGE_CHECK(first, last, check); + STACK_POP(first, middle, last, check); + continue; + } + + for(m = 0, len = MIN(middle - first, last - middle), half = len >> 1; + 0 < len; + len = half, half >>= 1) { + if(ss_compare(T, PA + GETIDX(*(middle + m + half)), + PA + GETIDX(*(middle - m - half - 1)), depth) < 0) { + m += half + 1; + half -= (len & 1) ^ 1; + } + } + + if(0 < m) { + lm = middle - m, rm = middle + m; + ss_blockswap(lm, middle, m); + l = r = middle, next = 0; + if(rm < last) { + if(*rm < 0) { + *rm = ~*rm; + if(first < lm) { for(; *--l < 0;) { } next |= 4; } + next |= 1; + } else if(first < lm) { + for(; *r < 0; ++r) { } + next |= 2; + } + } + + if((l - first) <= (last - r)) { + STACK_PUSH(r, rm, last, (next & 3) | (check & 4)); + middle = lm, last = l, check = (check & 3) | (next & 4); + } else { + if((next & 2) && (r == middle)) { next ^= 6; } + STACK_PUSH(first, lm, l, (check & 3) | (next & 4)); + first = r, middle = rm, check = (next & 3) | (check & 4); + } + } else { + if(ss_compare(T, PA + GETIDX(*(middle - 1)), PA + *middle, depth) == 0) { + *middle = ~*middle; + } + MERGE_CHECK(first, last, check); + STACK_POP(first, middle, last, check); + } + } +#undef STACK_SIZE +} + +#endif /* SS_BLOCKSIZE != 0 */ + + +/*---------------------------------------------------------------------------*/ + +/*- Function -*/ + +/* Substring sort */ +void +sssort(const sauchar_t *T, const saidx_t *PA, + saidx_t *first, saidx_t *last, + saidx_t *buf, saidx_t bufsize, + saidx_t depth, saidx_t n, saint_t lastsuffix) { + saidx_t *a; +#if SS_BLOCKSIZE != 0 + saidx_t *b, *middle, *curbuf; + saidx_t j, k, curbufsize, limit; +#endif + saidx_t i; + + if(lastsuffix != 0) { ++first; } + +#if SS_BLOCKSIZE == 0 + ss_mintrosort(T, PA, first, last, depth); +#else + if((bufsize < SS_BLOCKSIZE) && + (bufsize < (last - first)) && + (bufsize < (limit = ss_isqrt(last - first)))) { + if(SS_BLOCKSIZE < limit) { limit = SS_BLOCKSIZE; } + buf = middle = last - limit, bufsize = limit; + } else { + middle = last, limit = 0; + } + for(a = first, i = 0; SS_BLOCKSIZE < (middle - a); a += SS_BLOCKSIZE, ++i) { +#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE + ss_mintrosort(T, PA, a, a + SS_BLOCKSIZE, depth); +#elif 1 < SS_BLOCKSIZE + ss_insertionsort(T, PA, a, a + SS_BLOCKSIZE, depth); +#endif + curbufsize = last - (a + SS_BLOCKSIZE); + curbuf = a + SS_BLOCKSIZE; + if(curbufsize <= bufsize) { curbufsize = bufsize, curbuf = buf; } + for(b = a, k = SS_BLOCKSIZE, j = i; j & 1; b -= k, k <<= 1, j >>= 1) { + ss_swapmerge(T, PA, b - k, b, b + k, curbuf, curbufsize, depth); + } + } +#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE + ss_mintrosort(T, PA, a, middle, depth); +#elif 1 < SS_BLOCKSIZE + ss_insertionsort(T, PA, a, middle, depth); +#endif + for(k = SS_BLOCKSIZE; i != 0; k <<= 1, i >>= 1) { + if(i & 1) { + ss_swapmerge(T, PA, a - k, a, middle, buf, bufsize, depth); + a -= k; + } + } + if(limit != 0) { +#if SS_INSERTIONSORT_THRESHOLD < SS_BLOCKSIZE + ss_mintrosort(T, PA, middle, last, depth); +#elif 1 < SS_BLOCKSIZE + ss_insertionsort(T, PA, middle, last, depth); +#endif + ss_inplacemerge(T, PA, first, middle, last, depth); + } +#endif + + if(lastsuffix != 0) { + /* Insert last type B* suffix. */ + saidx_t PAi[2]; PAi[0] = PA[*(first - 1)], PAi[1] = n - 2; + for(a = first, i = *(first - 1); + (a < last) && ((*a < 0) || (0 < ss_compare(T, &(PAi[0]), PA + *a, depth))); + ++a) { + *(a - 1) = *a; + } + *(a - 1) = i; + } +} diff --git a/contrib/libdivsufsort/lib/trsort.c b/contrib/libdivsufsort/lib/trsort.c new file mode 100644 index 000000000000..6fe3e67baa4c --- /dev/null +++ b/contrib/libdivsufsort/lib/trsort.c @@ -0,0 +1,586 @@ +/* + * trsort.c for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#include "divsufsort_private.h" + + +/*- Private Functions -*/ + +static const saint_t lg_table[256]= { + -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 +}; + +static INLINE +saint_t +tr_ilg(saidx_t n) { +#if defined(BUILD_DIVSUFSORT64) + return (n >> 32) ? + ((n >> 48) ? + ((n >> 56) ? + 56 + lg_table[(n >> 56) & 0xff] : + 48 + lg_table[(n >> 48) & 0xff]) : + ((n >> 40) ? + 40 + lg_table[(n >> 40) & 0xff] : + 32 + lg_table[(n >> 32) & 0xff])) : + ((n & 0xffff0000) ? + ((n & 0xff000000) ? + 24 + lg_table[(n >> 24) & 0xff] : + 16 + lg_table[(n >> 16) & 0xff]) : + ((n & 0x0000ff00) ? + 8 + lg_table[(n >> 8) & 0xff] : + 0 + lg_table[(n >> 0) & 0xff])); +#else + return (n & 0xffff0000) ? + ((n & 0xff000000) ? + 24 + lg_table[(n >> 24) & 0xff] : + 16 + lg_table[(n >> 16) & 0xff]) : + ((n & 0x0000ff00) ? + 8 + lg_table[(n >> 8) & 0xff] : + 0 + lg_table[(n >> 0) & 0xff]); +#endif +} + + +/*---------------------------------------------------------------------------*/ + +/* Simple insertionsort for small size groups. */ +static +void +tr_insertionsort(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { + saidx_t *a, *b; + saidx_t t, r; + + for(a = first + 1; a < last; ++a) { + for(t = *a, b = a - 1; 0 > (r = ISAd[t] - ISAd[*b]);) { + do { *(b + 1) = *b; } while((first <= --b) && (*b < 0)); + if(b < first) { break; } + } + if(r == 0) { *b = ~*b; } + *(b + 1) = t; + } +} + + +/*---------------------------------------------------------------------------*/ + +static INLINE +void +tr_fixdown(const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size) { + saidx_t j, k; + saidx_t v; + saidx_t c, d, e; + + for(v = SA[i], c = ISAd[v]; (j = 2 * i + 1) < size; SA[i] = SA[k], i = k) { + d = ISAd[SA[k = j++]]; + if(d < (e = ISAd[SA[j]])) { k = j; d = e; } + if(d <= c) { break; } + } + SA[i] = v; +} + +/* Simple top-down heapsort. */ +static +void +tr_heapsort(const saidx_t *ISAd, saidx_t *SA, saidx_t size) { + saidx_t i, m; + saidx_t t; + + m = size; + if((size % 2) == 0) { + m--; + if(ISAd[SA[m / 2]] < ISAd[SA[m]]) { SWAP(SA[m], SA[m / 2]); } + } + + for(i = m / 2 - 1; 0 <= i; --i) { tr_fixdown(ISAd, SA, i, m); } + if((size % 2) == 0) { SWAP(SA[0], SA[m]); tr_fixdown(ISAd, SA, 0, m); } + for(i = m - 1; 0 < i; --i) { + t = SA[0], SA[0] = SA[i]; + tr_fixdown(ISAd, SA, 0, i); + SA[i] = t; + } +} + + +/*---------------------------------------------------------------------------*/ + +/* Returns the median of three elements. */ +static INLINE +saidx_t * +tr_median3(const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3) { + saidx_t *t; + if(ISAd[*v1] > ISAd[*v2]) { SWAP(v1, v2); } + if(ISAd[*v2] > ISAd[*v3]) { + if(ISAd[*v1] > ISAd[*v3]) { return v1; } + else { return v3; } + } + return v2; +} + +/* Returns the median of five elements. */ +static INLINE +saidx_t * +tr_median5(const saidx_t *ISAd, + saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5) { + saidx_t *t; + if(ISAd[*v2] > ISAd[*v3]) { SWAP(v2, v3); } + if(ISAd[*v4] > ISAd[*v5]) { SWAP(v4, v5); } + if(ISAd[*v2] > ISAd[*v4]) { SWAP(v2, v4); SWAP(v3, v5); } + if(ISAd[*v1] > ISAd[*v3]) { SWAP(v1, v3); } + if(ISAd[*v1] > ISAd[*v4]) { SWAP(v1, v4); SWAP(v3, v5); } + if(ISAd[*v3] > ISAd[*v4]) { return v4; } + return v3; +} + +/* Returns the pivot element. */ +static INLINE +saidx_t * +tr_pivot(const saidx_t *ISAd, saidx_t *first, saidx_t *last) { + saidx_t *middle; + saidx_t t; + + t = last - first; + middle = first + t / 2; + + if(t <= 512) { + if(t <= 32) { + return tr_median3(ISAd, first, middle, last - 1); + } else { + t >>= 2; + return tr_median5(ISAd, first, first + t, middle, last - 1 - t, last - 1); + } + } + t >>= 3; + first = tr_median3(ISAd, first, first + t, first + (t << 1)); + middle = tr_median3(ISAd, middle - t, middle, middle + t); + last = tr_median3(ISAd, last - 1 - (t << 1), last - 1 - t, last - 1); + return tr_median3(ISAd, first, middle, last); +} + + +/*---------------------------------------------------------------------------*/ + +typedef struct _trbudget_t trbudget_t; +struct _trbudget_t { + saidx_t chance; + saidx_t remain; + saidx_t incval; + saidx_t count; +}; + +static INLINE +void +trbudget_init(trbudget_t *budget, saidx_t chance, saidx_t incval) { + budget->chance = chance; + budget->remain = budget->incval = incval; +} + +static INLINE +saint_t +trbudget_check(trbudget_t *budget, saidx_t size) { + if(size <= budget->remain) { budget->remain -= size; return 1; } + if(budget->chance == 0) { budget->count += size; return 0; } + budget->remain += budget->incval - size; + budget->chance -= 1; + return 1; +} + + +/*---------------------------------------------------------------------------*/ + +static INLINE +void +tr_partition(const saidx_t *ISAd, + saidx_t *first, saidx_t *middle, saidx_t *last, + saidx_t **pa, saidx_t **pb, saidx_t v) { + saidx_t *a, *b, *c, *d, *e, *f; + saidx_t t, s; + saidx_t x = 0; + + for(b = middle - 1; (++b < last) && ((x = ISAd[*b]) == v);) { } + if(((a = b) < last) && (x < v)) { + for(; (++b < last) && ((x = ISAd[*b]) <= v);) { + if(x == v) { SWAP(*b, *a); ++a; } + } + } + for(c = last; (b < --c) && ((x = ISAd[*c]) == v);) { } + if((b < (d = c)) && (x > v)) { + for(; (b < --c) && ((x = ISAd[*c]) >= v);) { + if(x == v) { SWAP(*c, *d); --d; } + } + } + for(; b < c;) { + SWAP(*b, *c); + for(; (++b < c) && ((x = ISAd[*b]) <= v);) { + if(x == v) { SWAP(*b, *a); ++a; } + } + for(; (b < --c) && ((x = ISAd[*c]) >= v);) { + if(x == v) { SWAP(*c, *d); --d; } + } + } + + if(a <= d) { + c = b - 1; + if((s = a - first) > (t = b - a)) { s = t; } + for(e = first, f = b - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } + if((s = d - c) > (t = last - d - 1)) { s = t; } + for(e = b, f = last - s; 0 < s; --s, ++e, ++f) { SWAP(*e, *f); } + first += (b - a), last -= (d - c); + } + *pa = first, *pb = last; +} + +static +void +tr_copy(saidx_t *ISA, const saidx_t *SA, + saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, + saidx_t depth) { + /* sort suffixes of middle partition + by using sorted order of suffixes of left and right partition. */ + saidx_t *c, *d, *e; + saidx_t s, v; + + v = b - SA - 1; + for(c = first, d = a - 1; c <= d; ++c) { + if((0 <= (s = *c - depth)) && (ISA[s] == v)) { + *++d = s; + ISA[s] = d - SA; + } + } + for(c = last - 1, e = d + 1, d = b; e < d; --c) { + if((0 <= (s = *c - depth)) && (ISA[s] == v)) { + *--d = s; + ISA[s] = d - SA; + } + } +} + +static +void +tr_partialcopy(saidx_t *ISA, const saidx_t *SA, + saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, + saidx_t depth) { + saidx_t *c, *d, *e; + saidx_t s, v; + saidx_t rank, lastrank, newrank = -1; + + v = b - SA - 1; + lastrank = -1; + for(c = first, d = a - 1; c <= d; ++c) { + if((0 <= (s = *c - depth)) && (ISA[s] == v)) { + *++d = s; + rank = ISA[s + depth]; + if(lastrank != rank) { lastrank = rank; newrank = d - SA; } + ISA[s] = newrank; + } + } + + lastrank = -1; + for(e = d; first <= e; --e) { + rank = ISA[*e]; + if(lastrank != rank) { lastrank = rank; newrank = e - SA; } + if(newrank != rank) { ISA[*e] = newrank; } + } + + lastrank = -1; + for(c = last - 1, e = d + 1, d = b; e < d; --c) { + if((0 <= (s = *c - depth)) && (ISA[s] == v)) { + *--d = s; + rank = ISA[s + depth]; + if(lastrank != rank) { lastrank = rank; newrank = d - SA; } + ISA[s] = newrank; + } + } +} + +static +void +tr_introsort(saidx_t *ISA, const saidx_t *ISAd, + saidx_t *SA, saidx_t *first, saidx_t *last, + trbudget_t *budget) { +#define STACK_SIZE TR_STACKSIZE + struct { const saidx_t *a; saidx_t *b, *c; saint_t d, e; }stack[STACK_SIZE]; + saidx_t *a, *b, *c; + saidx_t t; + saidx_t v, x = 0; + saidx_t incr = ISAd - ISA; + saint_t limit, next; + saint_t ssize, trlink = -1; + + for(ssize = 0, limit = tr_ilg(last - first);;) { + + if(limit < 0) { + if(limit == -1) { + /* tandem repeat partition */ + tr_partition(ISAd - incr, first, first, last, &a, &b, last - SA - 1); + + /* update ranks */ + if(a < last) { + for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } + } + if(b < last) { + for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } + } + + /* push */ + if(1 < (b - a)) { + STACK_PUSH5(NULL, a, b, 0, 0); + STACK_PUSH5(ISAd - incr, first, last, -2, trlink); + trlink = ssize - 2; + } + if((a - first) <= (last - b)) { + if(1 < (a - first)) { + STACK_PUSH5(ISAd, b, last, tr_ilg(last - b), trlink); + last = a, limit = tr_ilg(a - first); + } else if(1 < (last - b)) { + first = b, limit = tr_ilg(last - b); + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } else { + if(1 < (last - b)) { + STACK_PUSH5(ISAd, first, a, tr_ilg(a - first), trlink); + first = b, limit = tr_ilg(last - b); + } else if(1 < (a - first)) { + last = a, limit = tr_ilg(a - first); + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } + } else if(limit == -2) { + /* tandem repeat copy */ + a = stack[--ssize].b, b = stack[ssize].c; + if(stack[ssize].d == 0) { + tr_copy(ISA, SA, first, a, b, last, ISAd - ISA); + } else { + if(0 <= trlink) { stack[trlink].d = -1; } + tr_partialcopy(ISA, SA, first, a, b, last, ISAd - ISA); + } + STACK_POP5(ISAd, first, last, limit, trlink); + } else { + /* sorted partition */ + if(0 <= *first) { + a = first; + do { ISA[*a] = a - SA; } while((++a < last) && (0 <= *a)); + first = a; + } + if(first < last) { + a = first; do { *a = ~*a; } while(*++a < 0); + next = (ISA[*a] != ISAd[*a]) ? tr_ilg(a - first + 1) : -1; + if(++a < last) { for(b = first, v = a - SA - 1; b < a; ++b) { ISA[*b] = v; } } + + /* push */ + if(trbudget_check(budget, a - first)) { + if((a - first) <= (last - a)) { + STACK_PUSH5(ISAd, a, last, -3, trlink); + ISAd += incr, last = a, limit = next; + } else { + if(1 < (last - a)) { + STACK_PUSH5(ISAd + incr, first, a, next, trlink); + first = a, limit = -3; + } else { + ISAd += incr, last = a, limit = next; + } + } + } else { + if(0 <= trlink) { stack[trlink].d = -1; } + if(1 < (last - a)) { + first = a, limit = -3; + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } + continue; + } + + if((last - first) <= TR_INSERTIONSORT_THRESHOLD) { + tr_insertionsort(ISAd, first, last); + limit = -3; + continue; + } + + if(limit-- == 0) { + tr_heapsort(ISAd, first, last - first); + for(a = last - 1; first < a; a = b) { + for(x = ISAd[*a], b = a - 1; (first <= b) && (ISAd[*b] == x); --b) { *b = ~*b; } + } + limit = -3; + continue; + } + + /* choose pivot */ + a = tr_pivot(ISAd, first, last); + SWAP(*first, *a); + v = ISAd[*first]; + + /* partition */ + tr_partition(ISAd, first, first + 1, last, &a, &b, v); + if((last - first) != (b - a)) { + next = (ISA[*a] != v) ? tr_ilg(b - a) : -1; + + /* update ranks */ + for(c = first, v = a - SA - 1; c < a; ++c) { ISA[*c] = v; } + if(b < last) { for(c = a, v = b - SA - 1; c < b; ++c) { ISA[*c] = v; } } + + /* push */ + if((1 < (b - a)) && (trbudget_check(budget, b - a))) { + if((a - first) <= (last - b)) { + if((last - b) <= (b - a)) { + if(1 < (a - first)) { + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + STACK_PUSH5(ISAd, b, last, limit, trlink); + last = a; + } else if(1 < (last - b)) { + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + first = b; + } else { + ISAd += incr, first = a, last = b, limit = next; + } + } else if((a - first) <= (b - a)) { + if(1 < (a - first)) { + STACK_PUSH5(ISAd, b, last, limit, trlink); + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + last = a; + } else { + STACK_PUSH5(ISAd, b, last, limit, trlink); + ISAd += incr, first = a, last = b, limit = next; + } + } else { + STACK_PUSH5(ISAd, b, last, limit, trlink); + STACK_PUSH5(ISAd, first, a, limit, trlink); + ISAd += incr, first = a, last = b, limit = next; + } + } else { + if((a - first) <= (b - a)) { + if(1 < (last - b)) { + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + STACK_PUSH5(ISAd, first, a, limit, trlink); + first = b; + } else if(1 < (a - first)) { + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + last = a; + } else { + ISAd += incr, first = a, last = b, limit = next; + } + } else if((last - b) <= (b - a)) { + if(1 < (last - b)) { + STACK_PUSH5(ISAd, first, a, limit, trlink); + STACK_PUSH5(ISAd + incr, a, b, next, trlink); + first = b; + } else { + STACK_PUSH5(ISAd, first, a, limit, trlink); + ISAd += incr, first = a, last = b, limit = next; + } + } else { + STACK_PUSH5(ISAd, first, a, limit, trlink); + STACK_PUSH5(ISAd, b, last, limit, trlink); + ISAd += incr, first = a, last = b, limit = next; + } + } + } else { + if((1 < (b - a)) && (0 <= trlink)) { stack[trlink].d = -1; } + if((a - first) <= (last - b)) { + if(1 < (a - first)) { + STACK_PUSH5(ISAd, b, last, limit, trlink); + last = a; + } else if(1 < (last - b)) { + first = b; + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } else { + if(1 < (last - b)) { + STACK_PUSH5(ISAd, first, a, limit, trlink); + first = b; + } else if(1 < (a - first)) { + last = a; + } else { + STACK_POP5(ISAd, first, last, limit, trlink); + } + } + } + } else { + if(trbudget_check(budget, last - first)) { + limit = tr_ilg(last - first), ISAd += incr; + } else { + if(0 <= trlink) { stack[trlink].d = -1; } + STACK_POP5(ISAd, first, last, limit, trlink); + } + } + } +#undef STACK_SIZE +} + + + +/*---------------------------------------------------------------------------*/ + +/*- Function -*/ + +/* Tandem repeat sort */ +void +trsort(saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth) { + saidx_t *ISAd; + saidx_t *first, *last; + trbudget_t budget; + saidx_t t, skip, unsorted; + + trbudget_init(&budget, tr_ilg(n) * 2 / 3, n); +/* trbudget_init(&budget, tr_ilg(n) * 3 / 4, n); */ + for(ISAd = ISA + depth; -n < *SA; ISAd += ISAd - ISA) { + first = SA; + skip = 0; + unsorted = 0; + do { + if((t = *first) < 0) { first -= t; skip += t; } + else { + if(skip != 0) { *(first + skip) = skip; skip = 0; } + last = SA + ISA[t] + 1; + if(1 < (last - first)) { + budget.count = 0; + tr_introsort(ISA, ISAd, SA, first, last, &budget); + if(budget.count != 0) { unsorted += budget.count; } + else { skip = first - last; } + } else if((last - first) == 1) { + skip = -1; + } + first = last; + } + } while(first < (SA + n)); + if(skip != 0) { *(first + skip) = skip; } + if(unsorted == 0) { break; } + } +} diff --git a/contrib/libdivsufsort/lib/utils.c b/contrib/libdivsufsort/lib/utils.c new file mode 100644 index 000000000000..90fb23efa89a --- /dev/null +++ b/contrib/libdivsufsort/lib/utils.c @@ -0,0 +1,381 @@ +/* + * utils.c for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#include "divsufsort_private.h" + + +/*- Private Function -*/ + +/* Binary search for inverse bwt. */ +static +saidx_t +binarysearch_lower(const saidx_t *A, saidx_t size, saidx_t value) { + saidx_t half, i; + for(i = 0, half = size >> 1; + 0 < size; + size = half, half >>= 1) { + if(A[i + half] < value) { + i += half + 1; + half -= (size & 1) ^ 1; + } + } + return i; +} + + +/*- Functions -*/ + +/* Burrows-Wheeler transform. */ +saint_t +bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *SA, + saidx_t n, saidx_t *idx) { + saidx_t *A, i, j, p, t; + saint_t c; + + /* Check arguments. */ + if((T == NULL) || (U == NULL) || (n < 0) || (idx == NULL)) { return -1; } + if(n <= 1) { + if(n == 1) { U[0] = T[0]; } + *idx = n; + return 0; + } + + if((A = SA) == NULL) { + i = divbwt(T, U, NULL, n); + if(0 <= i) { *idx = i; i = 0; } + return (saint_t)i; + } + + /* BW transform. */ + if(T == U) { + t = n; + for(i = 0, j = 0; i < n; ++i) { + p = t - 1; + t = A[i]; + if(0 <= p) { + c = T[j]; + U[j] = (j <= p) ? T[p] : (sauchar_t)A[p]; + A[j] = c; + j++; + } else { + *idx = i; + } + } + p = t - 1; + if(0 <= p) { + c = T[j]; + U[j] = (j <= p) ? T[p] : (sauchar_t)A[p]; + A[j] = c; + } else { + *idx = i; + } + } else { + U[0] = T[n - 1]; + for(i = 0; A[i] != 0; ++i) { U[i + 1] = T[A[i] - 1]; } + *idx = i + 1; + for(++i; i < n; ++i) { U[i] = T[A[i] - 1]; } + } + + if(SA == NULL) { + /* Deallocate memory. */ + free(A); + } + + return 0; +} + +/* Inverse Burrows-Wheeler transform. */ +saint_t +inverse_bw_transform(const sauchar_t *T, sauchar_t *U, saidx_t *A, + saidx_t n, saidx_t idx) { + saidx_t C[ALPHABET_SIZE]; + sauchar_t D[ALPHABET_SIZE]; + saidx_t *B; + saidx_t i, p; + saint_t c, d; + + /* Check arguments. */ + if((T == NULL) || (U == NULL) || (n < 0) || (idx < 0) || + (n < idx) || ((0 < n) && (idx == 0))) { + return -1; + } + if(n <= 1) { return 0; } + + if((B = A) == NULL) { + /* Allocate n*sizeof(saidx_t) bytes of memory. */ + if((B = (saidx_t *)malloc((size_t)n * sizeof(saidx_t))) == NULL) { return -2; } + } + + /* Inverse BW transform. */ + for(c = 0; c < ALPHABET_SIZE; ++c) { C[c] = 0; } + for(i = 0; i < n; ++i) { ++C[T[i]]; } + for(c = 0, d = 0, i = 0; c < ALPHABET_SIZE; ++c) { + p = C[c]; + if(0 < p) { + C[c] = i; + D[d++] = (sauchar_t)c; + i += p; + } + } + for(i = 0; i < idx; ++i) { B[C[T[i]]++] = i; } + for( ; i < n; ++i) { B[C[T[i]]++] = i + 1; } + for(c = 0; c < d; ++c) { C[c] = C[D[c]]; } + for(i = 0, p = idx; i < n; ++i) { + U[i] = D[binarysearch_lower(C, d, p)]; + p = B[p - 1]; + } + + if(A == NULL) { + /* Deallocate memory. */ + free(B); + } + + return 0; +} + +/* Checks the suffix array SA of the string T. */ +saint_t +sufcheck(const sauchar_t *T, const saidx_t *SA, + saidx_t n, saint_t verbose) { + saidx_t C[ALPHABET_SIZE]; + saidx_t i, p, q, t; + saint_t c; + + if(verbose) { fprintf(stderr, "sufcheck: "); } + + /* Check arguments. */ + if((T == NULL) || (SA == NULL) || (n < 0)) { + if(verbose) { fprintf(stderr, "Invalid arguments.\n"); } + return -1; + } + if(n == 0) { + if(verbose) { fprintf(stderr, "Done.\n"); } + return 0; + } + + /* check range: [0..n-1] */ + for(i = 0; i < n; ++i) { + if((SA[i] < 0) || (n <= SA[i])) { + if(verbose) { + fprintf(stderr, "Out of the range [0,%" PRIdSAIDX_T "].\n" + " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n", + n - 1, i, SA[i]); + } + return -2; + } + } + + /* check first characters. */ + for(i = 1; i < n; ++i) { + if(T[SA[i - 1]] > T[SA[i]]) { + if(verbose) { + fprintf(stderr, "Suffixes in wrong order.\n" + " T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d" + " > T[SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "]=%d\n", + i - 1, SA[i - 1], T[SA[i - 1]], i, SA[i], T[SA[i]]); + } + return -3; + } + } + + /* check suffixes. */ + for(i = 0; i < ALPHABET_SIZE; ++i) { C[i] = 0; } + for(i = 0; i < n; ++i) { ++C[T[i]]; } + for(i = 0, p = 0; i < ALPHABET_SIZE; ++i) { + t = C[i]; + C[i] = p; + p += t; + } + + q = C[T[n - 1]]; + C[T[n - 1]] += 1; + for(i = 0; i < n; ++i) { + p = SA[i]; + if(0 < p) { + c = T[--p]; + t = C[c]; + } else { + c = T[p = n - 1]; + t = q; + } + if((t < 0) || (p != SA[t])) { + if(verbose) { + fprintf(stderr, "Suffix in wrong position.\n" + " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T " or\n" + " SA[%" PRIdSAIDX_T "]=%" PRIdSAIDX_T "\n", + t, (0 <= t) ? SA[t] : -1, i, SA[i]); + } + return -4; + } + if(t != q) { + ++C[c]; + if((n <= C[c]) || (T[SA[C[c]]] != c)) { C[c] = -1; } + } + } + + if(1 <= verbose) { fprintf(stderr, "Done.\n"); } + return 0; +} + + +static +int +_compare(const sauchar_t *T, saidx_t Tsize, + const sauchar_t *P, saidx_t Psize, + saidx_t suf, saidx_t *match) { + saidx_t i, j; + saint_t r; + for(i = suf + *match, j = *match, r = 0; + (i < Tsize) && (j < Psize) && ((r = T[i] - P[j]) == 0); ++i, ++j) { } + *match = j; + return (r == 0) ? -(j != Psize) : r; +} + +/* Search for the pattern P in the string T. */ +saidx_t +sa_search(const sauchar_t *T, saidx_t Tsize, + const sauchar_t *P, saidx_t Psize, + const saidx_t *SA, saidx_t SAsize, + saidx_t *idx) { + saidx_t size, lsize, rsize, half; + saidx_t match, lmatch, rmatch; + saidx_t llmatch, lrmatch, rlmatch, rrmatch; + saidx_t i, j, k; + saint_t r; + + if(idx != NULL) { *idx = -1; } + if((T == NULL) || (P == NULL) || (SA == NULL) || + (Tsize < 0) || (Psize < 0) || (SAsize < 0)) { return -1; } + if((Tsize == 0) || (SAsize == 0)) { return 0; } + if(Psize == 0) { if(idx != NULL) { *idx = 0; } return SAsize; } + + for(i = j = k = 0, lmatch = rmatch = 0, size = SAsize, half = size >> 1; + 0 < size; + size = half, half >>= 1) { + match = MIN(lmatch, rmatch); + r = _compare(T, Tsize, P, Psize, SA[i + half], &match); + if(r < 0) { + i += half + 1; + half -= (size & 1) ^ 1; + lmatch = match; + } else if(r > 0) { + rmatch = match; + } else { + lsize = half, j = i, rsize = size - half - 1, k = i + half + 1; + + /* left part */ + for(llmatch = lmatch, lrmatch = match, half = lsize >> 1; + 0 < lsize; + lsize = half, half >>= 1) { + lmatch = MIN(llmatch, lrmatch); + r = _compare(T, Tsize, P, Psize, SA[j + half], &lmatch); + if(r < 0) { + j += half + 1; + half -= (lsize & 1) ^ 1; + llmatch = lmatch; + } else { + lrmatch = lmatch; + } + } + + /* right part */ + for(rlmatch = match, rrmatch = rmatch, half = rsize >> 1; + 0 < rsize; + rsize = half, half >>= 1) { + rmatch = MIN(rlmatch, rrmatch); + r = _compare(T, Tsize, P, Psize, SA[k + half], &rmatch); + if(r <= 0) { + k += half + 1; + half -= (rsize & 1) ^ 1; + rlmatch = rmatch; + } else { + rrmatch = rmatch; + } + } + + break; + } + } + + if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; } + return k - j; +} + +/* Search for the character c in the string T. */ +saidx_t +sa_simplesearch(const sauchar_t *T, saidx_t Tsize, + const saidx_t *SA, saidx_t SAsize, + saint_t c, saidx_t *idx) { + saidx_t size, lsize, rsize, half; + saidx_t i, j, k, p; + saint_t r; + + if(idx != NULL) { *idx = -1; } + if((T == NULL) || (SA == NULL) || (Tsize < 0) || (SAsize < 0)) { return -1; } + if((Tsize == 0) || (SAsize == 0)) { return 0; } + + for(i = j = k = 0, size = SAsize, half = size >> 1; + 0 < size; + size = half, half >>= 1) { + p = SA[i + half]; + r = (p < Tsize) ? T[p] - c : -1; + if(r < 0) { + i += half + 1; + half -= (size & 1) ^ 1; + } else if(r == 0) { + lsize = half, j = i, rsize = size - half - 1, k = i + half + 1; + + /* left part */ + for(half = lsize >> 1; + 0 < lsize; + lsize = half, half >>= 1) { + p = SA[j + half]; + r = (p < Tsize) ? T[p] - c : -1; + if(r < 0) { + j += half + 1; + half -= (lsize & 1) ^ 1; + } + } + + /* right part */ + for(half = rsize >> 1; + 0 < rsize; + rsize = half, half >>= 1) { + p = SA[k + half]; + r = (p < Tsize) ? T[p] - c : -1; + if(r <= 0) { + k += half + 1; + half -= (rsize & 1) ^ 1; + } + } + + break; + } + } + + if(idx != NULL) { *idx = (0 < (k - j)) ? j : i; } + return k - j; +} diff --git a/contrib/libexecinfo/backtrace.c b/contrib/libexecinfo/backtrace.c index 7dbf0bbb1755..b7a6e775c4bf 100644 --- a/contrib/libexecinfo/backtrace.c +++ b/contrib/libexecinfo/backtrace.c @@ -33,7 +33,6 @@ __RCSID("$NetBSD: backtrace.c,v 1.3 2013/08/29 14:58:56 christos Exp $"); #include <sys/param.h> #include <assert.h> -#define _WITH_DPRINTF #include <stdio.h> #include <string.h> #include <stdlib.h> diff --git a/contrib/libpcap/pcap-bpf.c b/contrib/libpcap/pcap-bpf.c index f5b66a457f1b..2f801bc1c3a7 100644 --- a/contrib/libpcap/pcap-bpf.c +++ b/contrib/libpcap/pcap-bpf.c @@ -431,6 +431,22 @@ pcap_create_interface(const char *device, char *ebuf) p->activate_op = pcap_activate_bpf; p->can_set_rfmon_op = pcap_can_set_rfmon_bpf; +#ifdef BIOCSTSTAMP + /* + * We claim that we support microsecond and nanosecond time + * stamps. + */ + p->tstamp_precision_count = 2; + p->tstamp_precision_list = malloc(2 * sizeof(u_int)); + if (p->tstamp_precision_list == NULL) { + snprintf(ebuf, PCAP_ERRBUF_SIZE, "malloc: %s", + pcap_strerror(errno)); + free(p); + return (NULL); + } + p->tstamp_precision_list[0] = PCAP_TSTAMP_PRECISION_MICRO; + p->tstamp_precision_list[1] = PCAP_TSTAMP_PRECISION_NANO; +#endif /* BIOCSTSTAMP */ return (p); } @@ -946,7 +962,11 @@ pcap_read_bpf(pcap_t *p, int cnt, pcap_handler callback, u_char *user) /* * Loop through each packet. */ +#ifdef BIOCSTSTAMP +#define bhp ((struct bpf_xhdr *)bp) +#else #define bhp ((struct bpf_hdr *)bp) +#endif ep = bp + cc; #ifdef PCAP_FDDIPAD pad = p->fddipad; @@ -1008,7 +1028,25 @@ pcap_read_bpf(pcap_t *p, int cnt, pcap_handler callback, u_char *user) if (pb->filtering_in_kernel || bpf_filter(p->fcode.bf_insns, datap, bhp->bh_datalen, caplen)) { struct pcap_pkthdr pkthdr; +#ifdef BIOCSTSTAMP + struct bintime bt; + bt.sec = bhp->bh_tstamp.bt_sec; + bt.frac = bhp->bh_tstamp.bt_frac; + if (p->opt.tstamp_precision == PCAP_TSTAMP_PRECISION_NANO) { + struct timespec ts; + + bintime2timespec(&bt, &ts); + pkthdr.ts.tv_sec = ts.tv_sec; + pkthdr.ts.tv_usec = ts.tv_nsec; + } else { + struct timeval tv; + + bintime2timeval(&bt, &tv); + pkthdr.ts.tv_sec = tv.tv_sec; + pkthdr.ts.tv_usec = tv.tv_usec; + } +#else pkthdr.ts.tv_sec = bhp->bh_tstamp.tv_sec; #ifdef _AIX /* @@ -1019,6 +1057,7 @@ pcap_read_bpf(pcap_t *p, int cnt, pcap_handler callback, u_char *user) #else pkthdr.ts.tv_usec = bhp->bh_tstamp.tv_usec; #endif +#endif /* BIOCSTSTAMP */ #ifdef PCAP_FDDIPAD if (caplen > pad) pkthdr.caplen = caplen - pad; @@ -2192,6 +2231,16 @@ pcap_activate_bpf(pcap_t *p) } } +#ifdef BIOCSTSTAMP + v = BPF_T_BINTIME; + if (ioctl(p->fd, BIOCSTSTAMP, &v) < 0) { + snprintf(p->errbuf, PCAP_ERRBUF_SIZE, "BIOCSTSTAMP: %s", + pcap_strerror(errno)); + status = PCAP_ERROR; + goto bad; + } +#endif /* BIOCSTSTAMP */ + if (ioctl(fd, BIOCGBLEN, (caddr_t)&v) < 0) { snprintf(p->errbuf, PCAP_ERRBUF_SIZE, "BIOCGBLEN: %s", pcap_strerror(errno)); diff --git a/contrib/llvm/projects/libunwind/src/Unwind-EHABI.cpp b/contrib/llvm/projects/libunwind/src/Unwind-EHABI.cpp index 5950c6902e38..ca7b43e113a7 100644 --- a/contrib/llvm/projects/libunwind/src/Unwind-EHABI.cpp +++ b/contrib/llvm/projects/libunwind/src/Unwind-EHABI.cpp @@ -572,7 +572,7 @@ static _Unwind_Reason_Code unwind_phase2(unw_context_t *uc, unw_cursor_t *cursor unw_get_reg(cursor, UNW_REG_SP, &sp); if (unw_get_proc_info(cursor, &frameInfo) != UNW_ESUCCESS) { _LIBUNWIND_TRACE_UNWINDING("unwind_phase2(ex_ojb=%p): unw_get_proc_info " - "failed => _URC_FATAL_PHASE1_ERROR\n", + "failed => _URC_FATAL_PHASE2_ERROR\n", static_cast<void *>(exception_object)); return _URC_FATAL_PHASE2_ERROR; } diff --git a/contrib/netbsd-tests/lib/libc/gen/t_basedirname.c b/contrib/netbsd-tests/lib/libc/gen/t_basedirname.c index 6c82cb471c27..184e660cc017 100644 --- a/contrib/netbsd-tests/lib/libc/gen/t_basedirname.c +++ b/contrib/netbsd-tests/lib/libc/gen/t_basedirname.c @@ -111,6 +111,7 @@ ATF_TC_BODY(basename_posix, tc) } else base = basename(NULL); +#ifdef __NetBSD__ /* * basename(3) is allowed to modify the input buffer. * However, that is considered hostile by some programs, @@ -127,6 +128,7 @@ ATF_TC_BODY(basename_posix, tc) test_basename_table[i].input); atf_tc_fail("Input buffer was modified."); } +#endif /* Make sure the result is correct. */ if (strcmp(test_basename_table[i].output, base) != 0) { @@ -162,6 +164,7 @@ ATF_TC_BODY(dirname_posix, tc) } else base = dirname(NULL); +#ifdef __NetBSD__ /* * dirname(3) is allowed to modify the input buffer. * However, that is considered hostile by some programs, @@ -178,6 +181,7 @@ ATF_TC_BODY(dirname_posix, tc) test_dirname_table[i].input); atf_tc_fail("Input buffer was modified."); } +#endif /* Make sure the result is correct. */ if (strcmp(test_dirname_table[i].output, base) != 0) { diff --git a/contrib/netbsd-tests/lib/libc/sys/t_timer_create.c b/contrib/netbsd-tests/lib/libc/sys/t_timer_create.c index cc853073ff45..364daaaf4687 100644 --- a/contrib/netbsd-tests/lib/libc/sys/t_timer_create.c +++ b/contrib/netbsd-tests/lib/libc/sys/t_timer_create.c @@ -116,6 +116,61 @@ timer_signal_create(clockid_t cid, bool expire) ATF_REQUIRE(timer_delete(t) == 0); } +#ifdef __FreeBSD__ +static void +timer_callback(union sigval value) +{ + timer_t *tp; + + tp = value.sival_ptr; + + if (*tp == t) + fail = false; +} + +static void +timer_thread_create(clockid_t cid, bool expire) +{ + struct itimerspec tim; + struct sigevent evt; + + t = 0; + fail = true; + + (void)memset(&evt, 0, sizeof(struct sigevent)); + (void)memset(&tim, 0, sizeof(struct itimerspec)); + + /* + * Create the timer (SIGEV_THREAD). + */ + evt.sigev_notify_function = timer_callback; + evt.sigev_value.sival_ptr = &t; + evt.sigev_notify = SIGEV_THREAD; + + ATF_REQUIRE(timer_create(cid, &evt, &t) == 0); + + /* + * Start the timer. + */ + tim.it_value.tv_sec = expire ? 5 : 1; + tim.it_value.tv_nsec = 0; + + ATF_REQUIRE(timer_settime(t, 0, &tim, NULL) == 0); + + (void)sleep(2); + + if (expire) { + if (!fail) + atf_tc_fail("timer fired too soon"); + } else { + if (fail) + atf_tc_fail("timer failed to fire"); + } + + ATF_REQUIRE(timer_delete(t) == 0); +} +#endif + ATF_TC(timer_create_err); ATF_TC_HEAD(timer_create_err, tc) { @@ -198,6 +253,64 @@ ATF_TC_BODY(timer_create_mono_expire, tc) timer_signal_create(CLOCK_MONOTONIC, true); } +ATF_TC(timer_thread_create_real); +ATF_TC_HEAD(timer_thread_create_real, tc) +{ + + atf_tc_set_md_var(tc, "descr", + "Checks timer_create(2) with CLOCK_REALTIME and sigevent(3), " + "SIGEV_THREAD"); +} + +#ifdef __FreeBSD__ +ATF_TC_BODY(timer_thread_create_real, tc) +{ + timer_thread_create(CLOCK_REALTIME, false); +} + +ATF_TC(timer_thread_create_mono); +ATF_TC_HEAD(timer_thread_create_mono, tc) +{ + + atf_tc_set_md_var(tc, "descr", + "Checks timer_create(2) with CLOCK_MONOTONIC and sigevent(3), " + "SIGEV_THREAD"); +} + +ATF_TC_BODY(timer_thread_create_mono, tc) +{ + timer_thread_create(CLOCK_MONOTONIC, false); +} + +ATF_TC(timer_thread_create_real_expire); +ATF_TC_HEAD(timer_thread_create_real_expire, tc) +{ + + atf_tc_set_md_var(tc, "descr", + "Checks timer_create(2) with CLOCK_REALTIME and sigevent(3), " + "SIGEV_THREAD, with expiration"); +} + +ATF_TC_BODY(timer_thread_create_real_expire, tc) +{ + timer_thread_create(CLOCK_REALTIME, true); +} + +ATF_TC(timer_thread_create_mono_expire); +ATF_TC_HEAD(timer_thread_create_mono_expire, tc) +{ + + atf_tc_set_md_var(tc, "descr", + "Checks timer_create(2) with CLOCK_MONOTONIC and sigevent(3), " + "SIGEV_THREAD, with expiration"); +} + +ATF_TC_BODY(timer_thread_create_mono_expire, tc) +{ + timer_thread_create(CLOCK_MONOTONIC, true); +} +#endif + ATF_TP_ADD_TCS(tp) { @@ -206,6 +319,12 @@ ATF_TP_ADD_TCS(tp) ATF_TP_ADD_TC(tp, timer_create_mono); ATF_TP_ADD_TC(tp, timer_create_real_expire); ATF_TP_ADD_TC(tp, timer_create_mono_expire); +#ifdef __FreeBSD__ + ATF_TP_ADD_TC(tp, timer_thread_create_real); + ATF_TP_ADD_TC(tp, timer_thread_create_mono); + ATF_TP_ADD_TC(tp, timer_thread_create_real_expire); + ATF_TP_ADD_TC(tp, timer_thread_create_mono_expire); +#endif return atf_no_error(); } diff --git a/contrib/ofed/usr.lib/libibverbs/config.h b/contrib/ofed/usr.lib/libibverbs/config.h index 688ab16590bb..dad24432a544 100644 --- a/contrib/ofed/usr.lib/libibverbs/config.h +++ b/contrib/ofed/usr.lib/libibverbs/config.h @@ -1,2 +1 @@ -#define _WITH_GETLINE #include <alloca.h> |