From owner-svn-src-stable@freebsd.org Sun Dec 11 06:08:03 2016 Return-Path: Delivered-To: svn-src-stable@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 83AC5C71941; Sun, 11 Dec 2016 06:08:03 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 51D169B6; Sun, 11 Dec 2016 06:08:03 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id uBB682fU069095; Sun, 11 Dec 2016 06:08:02 GMT (envelope-from delphij@FreeBSD.org) Received: (from delphij@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id uBB682JB069091; Sun, 11 Dec 2016 06:08:02 GMT (envelope-from delphij@FreeBSD.org) Message-Id: <201612110608.uBB682JB069091@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: delphij set sender to delphij@FreeBSD.org using -f From: Xin LI Date: Sun, 11 Dec 2016 06:08:02 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-11@freebsd.org Subject: svn commit: r309846 - in stable/11: contrib/libdivsufsort usr.bin/bsdiff/bsdiff X-SVN-Group: stable-11 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: SVN commit messages for all the -stable branches of the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 11 Dec 2016 06:08:03 -0000 Author: delphij Date: Sun Dec 11 06:08:01 2016 New Revision: 309846 URL: https://svnweb.freebsd.org/changeset/base/309846 Log: MFC r303285: Change bsdiff to use divsufsort suffix sort library instead of qsufsort, which is more efficient. Note that for now we do not create a separate library for libdivsufsort because it's not used anywhere else. Obtained from: Chromium Added: stable/11/contrib/libdivsufsort/ - copied from r303285, head/contrib/libdivsufsort/ stable/11/usr.bin/bsdiff/bsdiff/config.h - copied unchanged from r303285, head/usr.bin/bsdiff/bsdiff/config.h stable/11/usr.bin/bsdiff/bsdiff/divsufsort64.h - copied unchanged from r303285, head/usr.bin/bsdiff/bsdiff/divsufsort64.h Modified: stable/11/usr.bin/bsdiff/bsdiff/Makefile stable/11/usr.bin/bsdiff/bsdiff/bsdiff.c Directory Properties: stable/11/ (props changed) Modified: stable/11/usr.bin/bsdiff/bsdiff/Makefile ============================================================================== --- stable/11/usr.bin/bsdiff/bsdiff/Makefile Sun Dec 11 04:02:38 2016 (r309845) +++ stable/11/usr.bin/bsdiff/bsdiff/Makefile Sun Dec 11 06:08:01 2016 (r309846) @@ -1,6 +1,17 @@ # $FreeBSD$ -PROG= bsdiff +PROG= bsdiff + +# libdivsufsort configured with: +# cmake -DCMAKE_BUILD_TYPE="Release" -DBUILD_DIVSUFSORT64=ON +.PATH: ${.CURDIR}/../../../contrib/libdivsufsort/lib +CFLAGS+= -DHAVE_CONFIG_H=1 -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE +CFLAGS+= -D_LARGE_FILES -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS +CFLAGS+= -D__STDC_LIMIT_MACROS -DBUILD_DIVSUFSORT64 +CFLAGS+= -I${.CURDIR}/../../../contrib/libdivsufsort/include -I${.CURDIR} +SRCS= divsufsort.c sssort.c trsort.c utils.c + +SRCS+= bsdiff.c LIBADD= bz2 Modified: stable/11/usr.bin/bsdiff/bsdiff/bsdiff.c ============================================================================== --- stable/11/usr.bin/bsdiff/bsdiff/bsdiff.c Sun Dec 11 04:02:38 2016 (r309845) +++ stable/11/usr.bin/bsdiff/bsdiff/bsdiff.c Sun Dec 11 06:08:01 2016 (r309846) @@ -44,106 +44,11 @@ __FBSDID("$FreeBSD$"); #define O_BINARY 0 #endif -#define MIN(x,y) (((x)<(y)) ? (x) : (y)) - -static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h) -{ - off_t i,j,k,x,tmp,jj,kk; - - if(len<16) { - for(k=start;kstart) split(I,V,start,jj-start,h); - - for(i=0;ikk) split(I,V,kk,start+len-kk,h); -} - -static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize) -{ - off_t buckets[256]; - off_t i,h,len; - - for(i=0;i<256;i++) buckets[i]=0; - for(i=0;i0;i--) buckets[i]=buckets[i-1]; - buckets[0]=0; - - for(i=0;i + +#ifndef DIVSUFSORT_API +# ifdef DIVSUFSORT_BUILD_DLL +# define DIVSUFSORT_API +# else +# define DIVSUFSORT_API +# endif +#endif + +/*- Datatypes -*/ +#ifndef SAUCHAR_T +#define SAUCHAR_T +typedef uint8_t sauchar_t; +#endif /* SAUCHAR_T */ +#ifndef SAINT_T +#define SAINT_T +typedef int32_t saint_t; +#endif /* SAINT_T */ +#ifndef SAIDX64_T +#define SAIDX64_T +typedef int64_t saidx64_t; +#endif /* SAIDX64_T */ +#ifndef PRIdSAINT_T +#define PRIdSAINT_T PRId32 +#endif /* PRIdSAINT_T */ +#ifndef PRIdSAIDX64_T +#define PRIdSAIDX64_T PRId64 +#endif /* PRIdSAIDX64_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 +divsufsort64(const sauchar_t *T, saidx64_t *SA, saidx64_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 +saidx64_t +divbwt64(const sauchar_t *T, sauchar_t *U, saidx64_t *A, saidx64_t n); + +/** + * Returns the version of the divsufsort library. + * @return The version number string. + */ +DIVSUFSORT_API +const char * +divsufsort64_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_transform64(const sauchar_t *T, sauchar_t *U, + saidx64_t *SA /* can NULL */, + saidx64_t n, saidx64_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_transform64(const sauchar_t *T, sauchar_t *U, + saidx64_t *A /* can NULL */, + saidx64_t n, saidx64_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 +sufcheck64(const sauchar_t *T, const saidx64_t *SA, saidx64_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 +saidx64_t +sa_search64(const sauchar_t *T, saidx64_t Tsize, + const sauchar_t *P, saidx64_t Psize, + const saidx64_t *SA, saidx64_t SAsize, + saidx64_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 +saidx64_t +sa_simplesearch64(const sauchar_t *T, saidx64_t Tsize, + const saidx64_t *SA, saidx64_t SAsize, + saint_t c, saidx64_t *left); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT64_H */