From 5dced3d1b3deca80e01415a2e35dc7972dcbfae7 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 11:25:10 +0200 Subject: Adding upstream version 1.47.0. Signed-off-by: Daniel Baumann --- util/Makefile.in | 74 + util/all.exclude | 15 + util/android-README.version.in | 3 + util/android_config.h | 69 + util/android_types.h | 45 + util/copy_sparse.c | 228 +++ util/gen-android-files | 118 ++ util/gen-git-tarball | 17 + util/gen-sample-fs | 40 + util/gen-tarball.in | 50 + util/get-ver | 4 + util/install-symlink.in | 89 ++ util/libecho.c | 78 + util/mkutf8data.c | 3392 ++++++++++++++++++++++++++++++++++++++++ util/subst.c | 468 ++++++ util/subst.conf.in | 26 + util/symlinks.c | 391 +++++ util/ucd/README | 37 + 18 files changed, 5144 insertions(+) create mode 100644 util/Makefile.in create mode 100644 util/all.exclude create mode 100644 util/android-README.version.in create mode 100644 util/android_config.h create mode 100644 util/android_types.h create mode 100644 util/copy_sparse.c create mode 100755 util/gen-android-files create mode 100755 util/gen-git-tarball create mode 100755 util/gen-sample-fs create mode 100644 util/gen-tarball.in create mode 100755 util/get-ver create mode 100644 util/install-symlink.in create mode 100644 util/libecho.c create mode 100644 util/mkutf8data.c create mode 100644 util/subst.c create mode 100644 util/subst.conf.in create mode 100644 util/symlinks.c create mode 100644 util/ucd/README (limited to 'util') diff --git a/util/Makefile.in b/util/Makefile.in new file mode 100644 index 0000000..7ad18c0 --- /dev/null +++ b/util/Makefile.in @@ -0,0 +1,74 @@ +# +# Standard e2fsprogs prologue.... +# + +srcdir = @srcdir@ +top_srcdir = @top_srcdir@ +VPATH = @srcdir@ +top_builddir = .. +my_dir = util +INSTALL = @INSTALL@ +MKDIR_P = @MKDIR_P@ + +SRCS = $(srcdir)/subst.c $(srcdir)/mkutf8data.c + +@MCONFIG@ + +.c.o: + $(E) " CC $<" + $(Q) $(BUILD_CC) -c $(BUILD_CFLAGS) $< -o $@ + $(Q) $(CHECK_CMD) $(ALL_CFLAGS) $< + $(Q) $(CPPCHECK_CMD) $(CPPFLAGS) $< + +PROGS= subst symlinks mkutf8data + +all:: $(PROGS) gen-tarball + +dirpaths.h: + $(E) " CREATE dirpaths.h" + $(Q) echo "/* fake dirpaths.h for config.h */" > dirpaths.h + +subst.o: dirpaths.h + +subst: subst.o + $(E) " LD $@" + $(Q) $(BUILD_CC) $(BUILD_LDFLAGS) -o subst subst.o + +mkutf8data: mkutf8data.o + $(E) " LD $@" + $(Q) $(BUILD_CC) $(BUILD_LDFLAGS) -o mkutf8data mkutf8data.o + +copy_sparse: copy_sparse.o + $(E) " LD $@" + $(Q) $(BUILD_CC) $(BUILD_LDFLAGS) -o copy_sparse copy_sparse.o + +symlinks: symlinks.o + $(E) " LD $@" + $(Q) $(BUILD_CC) $(BUILD_LDFLAGS) -o symlinks symlinks.o + +gen-tarball: $(srcdir)/gen-tarball.in $(top_builddir)/config.status + $(E) " CONFIG.STATUS $@" + $(Q) cd $(top_builddir); CONFIG_FILES=util/gen-tarball ./config.status + $(Q) chmod +x gen-tarball + +tarballs: gen-tarball + sh gen-tarball debian + sh gen-tarball all + sh gen-tarball subset + +clean:: + $(RM) -f $(PROGS) \#* *.s *.o *.a *~ core *.tar.gz gen-tarball \ + copy-sparse dirpaths.h install-symlink mkutf8data + +mostlyclean: clean + +distclean: clean + $(RM) -f .depend Makefile $(srcdir)/TAGS $(srcdir)/Makefile.in.old + +# +++ Dependency line eater +++ +# +# Makefile dependencies follow. This must be the last section in +# the Makefile.in file +# +subst.o: $(srcdir)/subst.c $(top_builddir)/lib/config.h dirpaths.h +mkutf8data.o: $(srcdir)/mkutf8data.c diff --git a/util/all.exclude b/util/all.exclude new file mode 100644 index 0000000..d7d03b2 --- /dev/null +++ b/util/all.exclude @@ -0,0 +1,15 @@ +.git +.hg +.hgignore +.pc +patches +README.subset +build +build[^/]* +rpm.log +TODO +powerquest +.exclude-file +po/stamp-cat-id +po/cat-id-tbl.c +Meta diff --git a/util/android-README.version.in b/util/android-README.version.in new file mode 100644 index 0000000..c8a3217 --- /dev/null +++ b/util/android-README.version.in @@ -0,0 +1,3 @@ +URL: https://www.kernel.org/pub/linux/kernel/people/tytso/e2fsprogs/v@VER@/e2fsprogs-@FN@.tar.gz +Version: @FN@ +BugComponent: 95221 diff --git a/util/android_config.h b/util/android_config.h new file mode 100644 index 0000000..90b8f8a --- /dev/null +++ b/util/android_config.h @@ -0,0 +1,69 @@ +#ifndef __APPLE__ +#define HAVE_MALLOC_H 1 +#endif + +#define ROOT_SYSCONFDIR "/etc" + +#define ENABLE_LIBSPARSE 1 + +#define DISABLE_BACKTRACE 1 +#define HAVE_DIRENT_H 1 +#define HAVE_ERRNO_H 1 +#define HAVE_GETOPT_H 1 +#define HAVE_GETPWUID_R 1 +#define HAVE_INTPTR_T 1 +#define HAVE_INTTYPES_H 1 +#define HAVE_MMAP 1 +#define HAVE_SETJMP_H 1 +#define HAVE_SNPRINTF 1 +#define HAVE_STDLIB_H 1 +#define HAVE_STRCASECMP 1 +#define HAVE_STRDUP 1 +#define HAVE_STRINGS_H 1 +#define HAVE_STRNLEN 1 +#define HAVE_STRPTIME 1 +#define HAVE_SYSCONF 1 +#define HAVE_TYPE_SSIZE_T 1 +#define HAVE_UNISTD_H 1 +#define HAVE_UTIME_H 1 + +#define HAVE_SYS_STAT_H 1 +#if !defined(__APPLE__) +# define HAVE_SYS_SYSMACROS_H 1 +#endif +#define HAVE_SYS_TIME_H 1 +#define HAVE_SYS_TYPES_H 1 + +#if defined(_WIN32) +# define HAVE_LINUX_TYPES_H 1 +#endif +#if defined(__APPLE__) || defined(__linux__) +# define HAVE_FCNTL 1 +# define HAVE_FSYNC 1 +# define HAVE_GETPAGESIZE 1 +# define HAVE_NET_IF_H 1 +# define HAVE_NETINET_IN_H 1 +# define HAVE_PREAD 1 +# define HAVE_PWRITE 1 +# define HAVE_POSIX_MEMALIGN 1 +# define HAVE_SYS_IOCTL_H 1 +# define HAVE_SYS_MMAN_H 1 +# define HAVE_SYS_MOUNT_H 1 +# define HAVE_SYS_PARAM_H 1 +# define HAVE_SYS_RESOURCE_H 1 +# define HAVE_SYS_SELECT_H 1 +# define HAVE_SYS_WAIT_H 1 +#endif +#if defined(__linux__) +# define HAVE_EXT2_IOCTLS 1 +# define HAVE_FALLOCATE 1 +# define HAVE_LINUX_FD_H 1 +# define HAVE_LINUX_TYPES_H 1 +# define HAVE_LSEEK64 1 +# define HAVE_LSEEK64_PROTOTYPE 1 +# define HAVE_MNTENT_H 1 +# define HAVE_PREAD64 1 +# define HAVE_PWRITE64 1 +# define HAVE_SETMNTENT 1 +# define HAVE_SYS_PRCTL_H 1 +#endif diff --git a/util/android_types.h b/util/android_types.h new file mode 100644 index 0000000..5f05903 --- /dev/null +++ b/util/android_types.h @@ -0,0 +1,45 @@ +/* + * If linux/types.h is already been included, assume it has defined + * everything we need. (cross fingers) Other header files may have + * also defined the types that we need. + */ +#if (!defined(_LINUX_TYPES_H) && !defined(_BLKID_TYPES_H) && \ + !defined(_EXT2_TYPES_H) && !defined(_UUID_TYPES_H)) +#define _LINUX_TYPES_H + +typedef unsigned char __u8; +typedef __signed__ char __s8; +typedef unsigned short __u16; +typedef __signed__ short __s16; +typedef unsigned int __u32; +typedef __signed__ int __s32; +typedef unsigned long long __u64; +typedef __signed__ long long __s64; +#endif + +#include //uintptr_t + +/* endian checking stuff */ +#ifndef EXT2_ENDIAN_H_ +#define EXT2_ENDIAN_H_ + +#ifdef __CHECKER__ +#ifndef __bitwise +#define __bitwise __attribute__((bitwise)) +#endif +#define __force __attribute__((force)) +#else +#ifndef __bitwise +#define __bitwise +#endif +#define __force +#endif + +typedef __u16 __bitwise __le16; +typedef __u32 __bitwise __le32; +typedef __u64 __bitwise __le64; +typedef __u16 __bitwise __be16; +typedef __u32 __bitwise __be32; +typedef __u64 __bitwise __be64; + +#endif /* EXT2_ENDIAN_H_ */ diff --git a/util/copy_sparse.c b/util/copy_sparse.c new file mode 100644 index 0000000..cbab273 --- /dev/null +++ b/util/copy_sparse.c @@ -0,0 +1,228 @@ +/* + * copy_sparse.c -- copy a very large sparse files efficiently + * (requires root privileges) + * + * Copyright 2003, 2004 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#ifndef __linux__ +#include +#include + +int main(void) { + fputs("This program is only supported on Linux!\n", stderr); + exit(EXIT_FAILURE); +} +#else +#define _LARGEFILE64_SOURCE + +#include +#include +#include +#include +#include +#include +#include +#ifdef HAVE_GETOPT_H +#include +#else +extern char *optarg; +extern int optind; +#endif +#include +#include +#include +#include +#include + +int verbose = 0; + +#define FIBMAP _IO(0x00,1) /* bmap access */ +#define FIGETBSZ _IO(0x00,2) /* get the block size used for bmap */ + +static unsigned long get_bmap(int fd, unsigned long block) +{ + int ret; + unsigned long b; + + b = block; + ret = ioctl(fd, FIBMAP, &b); + if (ret < 0) { + if (errno == EPERM) { + fprintf(stderr, "No permission to use FIBMAP ioctl; must have root privileges\n"); + exit(1); + } + perror("FIBMAP"); + } + return b; +} + +static int full_read(int fd, char *buf, size_t count) +{ + int got, total = 0; + int pass = 0; + + while (count > 0) { + got = read(fd, buf, count); + if (got == -1) { + if ((errno == EINTR) || (errno == EAGAIN)) + continue; + return total ? total : -1; + } + if (got == 0) { + if (pass++ >= 3) + return total; + continue; + } + pass = 0; + buf += got; + total += got; + count -= got; + } + return total; +} + +static void copy_sparse_file(const char *src, const char *dest) +{ + struct stat64 fileinfo; + long lb, i, fd, ofd, bs, block, numblocks; + ssize_t got, got2; + off64_t offset = 0, should_be; + char *buf; + + if (verbose) + printf("Copying sparse file from %s to %s\n", src, dest); + + if (strcmp(src, "-")) { + if (stat64(src, &fileinfo) < 0) { + perror("stat"); + exit(1); + } + if (!S_ISREG(fileinfo.st_mode)) { + printf("%s: Not a regular file\n", src); + exit(1); + } + fd = open(src, O_RDONLY | O_LARGEFILE); + if (fd < 0) { + perror("open"); + exit(1); + } + if (ioctl(fd, FIGETBSZ, &bs) < 0) { + perror("FIGETBSZ"); + close(fd); + exit(1); + } + if (bs < 0) { + printf("%s: Invalid block size: %ld\n", src, bs); + exit(1); + } + if (verbose) + printf("Blocksize of file %s is %ld\n", src, bs); + numblocks = (fileinfo.st_size + (bs-1)) / bs; + if (verbose) + printf("File size of %s is %lld (%ld blocks)\n", src, + (long long) fileinfo.st_size, numblocks); + } else { + fd = 0; + bs = 1024; + } + + ofd = open(dest, O_WRONLY|O_CREAT|O_TRUNC|O_LARGEFILE, 0777); + if (ofd < 0) { + perror(dest); + exit(1); + } + + buf = malloc(bs); + if (!buf) { + fprintf(stderr, "Couldn't allocate buffer"); + exit(1); + } + + for (lb = 0; !fd || lb < numblocks; lb++) { + if (fd) { + block = get_bmap(fd, lb); + if (!block) + continue; + should_be = ((off64_t) lb) * bs; + if (offset != should_be) { + if (verbose) + printf("Seeking to %lld\n", should_be); + if (lseek64(fd, should_be, SEEK_SET) == (off_t) -1) { + perror("lseek src"); + exit(1); + } + if (lseek64(ofd, should_be, SEEK_SET) == (off_t) -1) { + perror("lseek dest"); + exit(1); + } + offset = should_be; + } + } + got = full_read(fd, buf, bs); + + if (fd == 0 && got == 0) + break; + + if (got == bs) { + for (i=0; i < bs; i++) + if (buf[i]) + break; + if (i == bs) { + lseek(ofd, bs, SEEK_CUR); + offset += bs; + continue; + } + } + got2 = write(ofd, buf, got); + if (got != got2) { + printf("short write\n"); + exit(1); + } + offset += got; + } + offset = fileinfo.st_size; + if (fstat64(ofd, &fileinfo) < 0) { + perror("fstat"); + exit(1); + } + if (fileinfo.st_size != offset) { + lseek64(ofd, offset-1, SEEK_CUR); + buf[0] = 0; + write(ofd, buf, 1); + } + close(fd); + close(ofd); +} + +static void usage(const char *progname) +{ + fprintf(stderr, "Usage: %s [-v] source_file destination_file\n", progname); + exit(1); +} + +int main(int argc, char**argv) +{ + int c; + + while ((c = getopt(argc, argv, "v")) != EOF) + switch (c) { + case 'v': + verbose++; + break; + default: + usage(argv[0]); + break; + } + if (optind+2 != argc) + usage(argv[0]); + copy_sparse_file(argv[optind], argv[optind+1]); + + return 0; +} +#endif diff --git a/util/gen-android-files b/util/gen-android-files new file mode 100755 index 0000000..cab4e8d --- /dev/null +++ b/util/gen-android-files @@ -0,0 +1,118 @@ +#!/bin/sh + +ANDROID_GENERATED_FILES="lib/ext2fs/ext2_err.c lib/ext2fs/ext2_err.h \ + lib/ss/ss_err.c lib/ss/ss_err.h lib/support/prof_err.c \ + lib/support/prof_err.h \ + lib/blkid/blkid_types.h lib/uuid/uuid_types.h \ + lib/ext2fs/ext2_types.h lib/config.h lib/blkid/blkid.h \ + lib/uuid/uuid.h lib/ext2fs/crc32c_table.h misc/default_profile.c \ + lib/ss/std_rqs.c debugfs/debug_cmds.c debugfs/ro_debug_cmds.c \ + debugfs/extent_cmds.c debugfs/e2freefrag.c \ + debugfs/recovery.c debugfs/revoke.c \ + MODULE_LICENSE_GPL README.version" + +SS_DIR=$(pwd)/lib/ss +MK_CMDS=/tmp/mk_cmds$$.sh + +sed -e "s/@AWK@/awk/" < $SS_DIR/mk_cmds.sh.in \ + | sed -e "s/@SED@/sed/" > $MK_CMDS + +sed -e "s/@E2FSPROGS_VERSION@/$(git describe)/" < lib/ext2fs/ext2_err.et.in > lib/ext2fs/ext2_err.et + +for i in lib/ss/ss_err lib/support/prof_err lib/ext2fs/ext2_err +do + rm -f $i.c $i.h + awk -f lib/et/et_c.awk outfile=$i.c outfn=$(basename $i.c) $i.et + awk -f lib/et/et_h.awk outfile=$i.h outfn=$(basename $i.h) $i.et +done + +for i in lib/ss/std_rqs debugfs/debug_cmds debugfs/ro_debug_cmds \ + debugfs/extent_cmds +do + _SS_DIR_OVERRIDE=lib/ss /bin/sh $MK_CMDS $i.ct + mv -f $(basename $i).c $i.c +done + +rm -f $MK_CMDS + +cp lib/blkid/blkid.h.in lib/blkid/blkid.h +cp lib/uuid/uuid.h.in lib/uuid/uuid.h + +cp util/android_types.h lib/ext2fs/ext2_types.h +cp util/android_types.h lib/blkid/blkid_types.h +cp util/android_types.h lib/uuid/uuid_types.h +# Copied header files having exactly same content results in debug output +# differences on RBE. Hence modify the #define's appropriately. +sed -i 's/#define _LINUX_TYPES_H/#define _BLKID_TYPES_H/g' lib/blkid/blkid_types.h +sed -i 's/#define _LINUX_TYPES_H/#define _EXT2_TYPES_H/g' lib/ext2fs/ext2_types.h +sed -i 's/#define _LINUX_TYPES_H/#define _UUID_TYPES_H/g' lib/uuid/uuid_types.h + +cp util/android_config.h lib/config.h +cp misc/e2freefrag.c debugfs/ +cp e2fsck/recovery.c e2fsck/revoke.c debugfs/ + +gcc -o gen_crc32ctable lib/ext2fs/gen_crc32ctable.c +./gen_crc32ctable > lib/ext2fs/crc32c_table.h + +awk -f misc/profile-to-c.awk < misc/mke2fs.conf.in > misc/default_profile.c + +rm -f ./gen_crc32table ./gen_crc32ctable lib/ext2fs/ext2_err.et + +touch MODULE_LICENSE_GPL + +E2FSPROGS_VERSION=`grep E2FSPROGS_VERSION version.h \ + | awk '{print $3}' | tr \" " " | awk '{print $1}'` +DATE=`grep E2FSPROGS_DATE version.h | awk '{print $3}' \ + | tr \" " "` +E2FSPROGS_DAY=$(echo $DATE | awk -F- '{print $1}' | sed -e '/^[1-9]$/s/^/0/') +MONTH=`echo $DATE | awk -F- '{print $2}'` +YEAR=`echo $DATE | awk -F- '{print $3}'` + +if expr $YEAR ">" 1900 > /dev/null ; then + E2FSPROGS_YEAR=$YEAR +elif expr $YEAR ">" 90 >/dev/null ; then + E2FSPROGS_YEAR=19$YEAR +else + E2FSPROGS_YEAR=20$YEAR +fi + +case $MONTH in +Jan) MONTH_NUM=01; E2FSPROGS_MONTH="January" ;; +Feb) MONTH_NUM=02; E2FSPROGS_MONTH="February" ;; +Mar) MONTH_NUM=03; E2FSPROGS_MONTH="March" ;; +Apr) MONTH_NUM=04; E2FSPROGS_MONTH="April" ;; +May) MONTH_NUM=05; E2FSPROGS_MONTH="May" ;; +Jun) MONTH_NUM=06; E2FSPROGS_MONTH="June" ;; +Jul) MONTH_NUM=07; E2FSPROGS_MONTH="July" ;; +Aug) MONTH_NUM=08; E2FSPROGS_MONTH="August" ;; +Sep) MONTH_NUM=09; E2FSPROGS_MONTH="September" ;; +Oct) MONTH_NUM=10; E2FSPROGS_MONTH="October" ;; +Nov) MONTH_NUM=11; E2FSPROGS_MONTH="November" ;; +Dec) MONTH_NUM=12; E2FSPROGS_MONTH="December" ;; +*) MONTH_NUM=13; E2FSPROGS_MONTH="UNKNOWN" ;; +esac + +base_ver=`echo $E2FSPROGS_VERSION | \ + sed -e 's/-WIP//' -e 's/pre-//' -e 's/-PLUS//'` + +date_spec=${E2FSPROGS_YEAR}${MONTH_NUM}${E2FSPROGS_DAY} + +case $E2FSPROGS_VERSION in +*-WIP|pre-*) + VER="$base_ver-WIP-$date_spec" + FN="$base_ver~WIP.$E2FSPROGS_YEAR.$MONTH_NUM.$E2FSPROGS_DAY" + ;; +*) + VER="$base_ver" + FN="$base_ver" + ;; +esac + +sed -e "s/@VER@/$VER/g" -e "s/@FN@/$FN/" < util/android-README.version.in > README.version + +git add -f $ANDROID_GENERATED_FILES +if test -f COPYING +then + git mv COPYING NOTICE +fi +git commit -m "Update generated files for Android" diff --git a/util/gen-git-tarball b/util/gen-git-tarball new file mode 100755 index 0000000..a959c4a --- /dev/null +++ b/util/gen-git-tarball @@ -0,0 +1,17 @@ +#!/bin/bash +# +# Generate the e2fsprogs release tar ball +# + +commit=HEAD + +if test -n "$1" ; then + commit="$1" +fi + +ver=`git show ${commit}:version.h | grep E2FSPROGS_VERSION \ + | awk '{print $3}' | tr \" " " | awk '{print $1}'` +fn=e2fsprogs-${ver}.tar.gz + +git archive --prefix=e2fsprogs-${ver}/ ${commit} | gzip -9n > $fn +echo "Generated $fn" diff --git a/util/gen-sample-fs b/util/gen-sample-fs new file mode 100755 index 0000000..8e13916 --- /dev/null +++ b/util/gen-sample-fs @@ -0,0 +1,40 @@ +#!/bin/bash + +MNT=/mnt +FS=/tmp/foo.img + +cp /dev/null $FS +mke2fs -q -t ext4 -O inline_data,^has_journal -I 256 -b 4096 -N 64 $FS 256 +mount -t ext4 $FS $MNT +ln -s symlink_data $MNT/symlink +for i in 30 70 500 1023 1024; do + ln -s /$(perl -e "print 'x' x $i;") $MNT/l_$i +done +touch $MNT/acl +setfacl -m u:daemon:r $MNT/acl +setfacl -m u:bin:rx $MNT/acl +setfacl -m g:mail:rw $MNT/acl +setfacl -m g:daemon:r $MNT/acl +touch $MNT/simple_acl +setfacl -m u:daemon:r $MNT/simple_acl +touch $MNT/xattr +attr -q -s foo -V bar $MNT/xattr +echo -e "one\n\ttwo" | attr -q -s quux $MNT/xattr +echo -e "abc\001\002\003" | attr -q -s def $MNT/xattr +echo file_data > $MNT/small_inline +a="I am a very model of a modern major general;" +a="$a I've information vegetable, animal and mineral" +echo $a > $MNT/big_inline +mkdir $MNT/sdir +touch $MNT/sdir/1 +touch $MNT/sdir/2 +touch $MNT/sdir/3 +touch $MNT/sdir/4 +mkdir $MNT/mdir +touch $MNT/mdir/1 +touch $MNT/mdir/2 +touch $MNT/mdir/3 +touch $MNT/mdir/4 +touch $MNT/mdir/5 +umount $MNT +e2fsck -fp $FS diff --git a/util/gen-tarball.in b/util/gen-tarball.in new file mode 100644 index 0000000..997bd93 --- /dev/null +++ b/util/gen-tarball.in @@ -0,0 +1,50 @@ +#!/bin/sh +# +# This script is used to generate the distribution tarball +# +srcdir=@srcdir@ +top_srcdir=@top_srcdir@ +top_dir=`cd $top_srcdir; pwd` +base_ver=`echo @E2FSPROGS_VERSION@ | sed -e 's/-WIP//' -e 's/pre-//' -e 's/-PLUS//'` +base_e2fsprogs=`basename $top_dir` +exclude=/tmp/exclude$$ +GZIP=gzip + +# +# This hack is needed because texi2dvi blows up horribly if there are +# any '~' characters in the directory pathname. So we kludge around it by +# using a non-standard directory name for WIP releases. dpkg-source +# complains, but life goes on. +# +deb_pkgver=`echo @E2FSPROGS_PKGVER@ | sed -e 's/~/-/g'` + +case $1 in + debian|ubuntu) + SRCROOT="e2fsprogs-$deb_pkgver" + tarout="e2fsprogs_@E2FSPROGS_PKGVER@.orig.tar.gz" + ;; + all|*) + SRCROOT="e2fsprogs-$base_ver" + tarout="$SRCROOT.tar.gz" + ;; +esac + +if test -z "$SOURCE_DATE_EPOCH" ; then + export SOURCE_DATE_EPOCH=$(cd $top_srcdir; git log -1 --pretty=%ct) +fi + +(cd $top_srcdir/.. ; find $base_e2fsprogs \( -name \*~ -o -name \*.orig \ + -o -name CVS -o -name \*.rej -o -name Makefile.pq \ + -o -name TAGS -o -name \*.old -o -name SCCS \ + -o -name changed-files -o -name .#\* -o -name \*.tar.gz \ + -o -name autom4te.cache \) \ + -print) > $exclude +sed -e "s;^;$base_e2fsprogs/;" < $srcdir/all.exclude >> $exclude + +(cd $top_srcdir/.. ; \ + tar -c -f - -X $exclude --sort=name --owner=0 --group=0 \ + --transform "flags=r;s|^$base_e2fsprogs|$SRCROOT|" \ + --numeric-owner --mtime="@${SOURCE_DATE_EPOCH}" $base_e2fsprogs) \ + | $GZIP -9n -c > $tarout +$GZIP -ln $tarout +rm -f "$exclude" diff --git a/util/get-ver b/util/get-ver new file mode 100755 index 0000000..ade7d22 --- /dev/null +++ b/util/get-ver @@ -0,0 +1,4 @@ +#!/bin/sh + +ver=$(git describe --always --dirty); echo "e2fsprogs $ver ($(git log -1 --pretty=%cD))" + diff --git a/util/install-symlink.in b/util/install-symlink.in new file mode 100644 index 0000000..24341b8 --- /dev/null +++ b/util/install-symlink.in @@ -0,0 +1,89 @@ +#!/bin/sh +# +# install-symlink source destination destdir +# + +SYMLINKS=symlinks +LN_S="@LN_S@" +RM="@RM@" +FORCE_RELATIVE=NO +FORCE_ABSOLUTE=NO + +while echo $1 | grep -q -- ^- ; +do + case $1 in + --relative) + FORCE_RELATIVE=YES + ;; + --absolute) + FORCE_ABSOLUTE=YES + ;; + --debian) + FORCE_ABSOLUTE=NO + FORCE_RELATIVE=NO + ;; + --symlinks=*) + SYMLINKS=$(echo $1 | sed -e 's/--symlinks=//') + ;; + *) + echo "Unknown option $1" + exit 1 + ;; + esac + shift; +done + + +FIX_SYMLINK="$SYMLINKS -c" + +SRC="$1" +DEST="$2" +DESTDIR="$3" + +if ! echo $SRC | grep -q ^/ ; then + echo $SRC: Source pathname must be absolute + exit 1 +fi + +if ! echo $DEST | grep -q ^/ ; then + echo $DEST: Destination pathname must be absolute + exit 1 +fi + +if ! test -e "$DESTDIR$SRC" ; then + echo $DESTDIR$SRC: file or directory does not exist + exit 1 +fi + +$RM -f "$DESTDIR$DEST" + +if test "$LN_S" != "ln -s" ; then + $LN_S "$DESTDIR$SRC" "$DESTDIR$DEST" + exit 0 +fi + +if test $(dirname "$SRC") = $(dirname "$DEST") ; then + $LN_S "$(basename "$SRC")" "$DESTDIR$DEST" + exit 0 +fi + +TOP_SRC=$(echo $SRC | awk -F/ '{print $2}') +TOP_DEST=$(echo $DEST | awk -F/ '{print $2}') + +if test $FORCE_RELATIVE = YES ; then + TOP_SRC=FORCE + TOP_DEST=FORCE +fi + +if test $FORCE_ABSOLUTE = YES ; then + TOP_SRC=FORCE + TOP_DEST=FORCE_ABSOLUTE +fi + +if test $TOP_SRC != $TOP_DEST ; then + $LN_S "$SRC" "$DESTDIR$DEST" +else + $LN_S "$DESTDIR$SRC" "$DESTDIR$DEST" + $FIX_SYMLINK "$DESTDIR$DEST" +fi + diff --git a/util/libecho.c b/util/libecho.c new file mode 100644 index 0000000..352ce1e --- /dev/null +++ b/util/libecho.c @@ -0,0 +1,78 @@ +/* + * libecho.c + * + * For each argument on the command line, echo it. Should expand + * DOS wildcards correctly. + * + * Syntax: libecho [-p prefix] list... + */ +#include +#include +#include + +void echo_files(char *, char *); + +int +main(int argc, char *argv[]) +{ + int i; + char *prefix; + + prefix = ""; + + if (argc < 2) { + fprintf(stderr, "Usage: libecho [-p prefix] list...\n"); + return 1; + } + + for (i = 1 ; i < argc ; i++) + if (!stricmp(argv[i], "-p")) + prefix = argv[++i]; + else + echo_files(prefix, argv[i]); + + return 0; +} + +void +echo_files(char *prefix, char *f) +{ + long ff; + struct _finddata_t fdt; + char *slash; + char filepath[256]; + + /* + * We're unix based quite a bit here. Look for normal slashes and + * make them reverse slashes. + */ + while((slash = strrchr(f, '/')) != NULL) + *slash = '\\'; + + strcpy(filepath, f); + + slash = strrchr(filepath, '\\'); + + if (slash) { + slash++; + *slash = 0; + } else { + filepath[0] = '\0'; + } + + ff = _findfirst(f, &fdt); + + if (ff < 0) { + printf("%s%s\n", prefix, f); + return; + } + + printf("%s%s%s\n", prefix, filepath, fdt.name); + + for (;;) { + if (_findnext(ff, &fdt) < 0) + break; + printf("%s%s%s\n", prefix, filepath, fdt.name); + } + _findclose(ff); +} diff --git a/util/mkutf8data.c b/util/mkutf8data.c new file mode 100644 index 0000000..2af25ac --- /dev/null +++ b/util/mkutf8data.c @@ -0,0 +1,3392 @@ +/* + * Copyright (c) 2014 SGI. + * All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +/* Generator for a compact trie for unicode normalization */ + +#include +#include +#include +#include +#include +#include +#include +#include + +/* Default names of the in- and output files. */ + +#define AGE_NAME "DerivedAge.txt" +#define CCC_NAME "DerivedCombiningClass.txt" +#define PROP_NAME "DerivedCoreProperties.txt" +#define DATA_NAME "UnicodeData.txt" +#define FOLD_NAME "CaseFolding.txt" +#define NORM_NAME "NormalizationCorrections.txt" +#define TEST_NAME "NormalizationTest.txt" +#define UTF8_NAME "utf8data.h" + +const char *age_name = AGE_NAME; +const char *ccc_name = CCC_NAME; +const char *prop_name = PROP_NAME; +const char *data_name = DATA_NAME; +const char *fold_name = FOLD_NAME; +const char *norm_name = NORM_NAME; +const char *test_name = TEST_NAME; +const char *utf8_name = UTF8_NAME; + +int verbose = 0; + +/* An arbitrary line size limit on input lines. */ + +#define LINESIZE 1024 +char line[LINESIZE]; +char buf0[LINESIZE]; +char buf1[LINESIZE]; +char buf2[LINESIZE]; +char buf3[LINESIZE]; + +const char *argv0; + +/* ------------------------------------------------------------------ */ + +/* + * Unicode version numbers consist of three parts: major, minor, and a + * revision. These numbers are packed into an unsigned int to obtain + * a single version number. + * + * To save space in the generated trie, the unicode version is not + * stored directly, instead we calculate a generation number from the + * unicode versions seen in the DerivedAge file, and use that as an + * index into a table of unicode versions. + */ +#define UNICODE_MAJ_SHIFT (16) +#define UNICODE_MIN_SHIFT (8) + +#define UNICODE_MAJ_MAX ((unsigned short)-1) +#define UNICODE_MIN_MAX ((unsigned char)-1) +#define UNICODE_REV_MAX ((unsigned char)-1) + +#define UNICODE_AGE(MAJ,MIN,REV) \ + (((unsigned int)(MAJ) << UNICODE_MAJ_SHIFT) | \ + ((unsigned int)(MIN) << UNICODE_MIN_SHIFT) | \ + ((unsigned int)(REV))) + +unsigned int *ages; +int ages_count; + +unsigned int unicode_maxage; + +static int age_valid(unsigned int major, unsigned int minor, + unsigned int revision) +{ + if (major > UNICODE_MAJ_MAX) + return 0; + if (minor > UNICODE_MIN_MAX) + return 0; + if (revision > UNICODE_REV_MAX) + return 0; + return 1; +} + +/* ------------------------------------------------------------------ */ + +/* + * utf8trie_t + * + * A compact binary tree, used to decode UTF-8 characters. + * + * Internal nodes are one byte for the node itself, and up to three + * bytes for an offset into the tree. The first byte contains the + * following information: + * NEXTBYTE - flag - advance to next byte if set + * BITNUM - 3 bit field - the bit number to tested + * OFFLEN - 2 bit field - number of bytes in the offset + * if offlen == 0 (non-branching node) + * RIGHTPATH - 1 bit field - set if the following node is for the + * right-hand path (tested bit is set) + * TRIENODE - 1 bit field - set if the following node is an internal + * node, otherwise it is a leaf node + * if offlen != 0 (branching node) + * LEFTNODE - 1 bit field - set if the left-hand node is internal + * RIGHTNODE - 1 bit field - set if the right-hand node is internal + * + * Due to the way utf8 works, there cannot be branching nodes with + * NEXTBYTE set, and moreover those nodes always have a righthand + * descendant. + */ +typedef unsigned char utf8trie_t; +#define BITNUM 0x07 +#define NEXTBYTE 0x08 +#define OFFLEN 0x30 +#define OFFLEN_SHIFT 4 +#define RIGHTPATH 0x40 +#define TRIENODE 0x80 +#define RIGHTNODE 0x40 +#define LEFTNODE 0x80 + +/* + * utf8leaf_t + * + * The leaves of the trie are embedded in the trie, and so the same + * underlying datatype, unsigned char. + * + * leaf[0]: The unicode version, stored as a generation number that is + * an index into utf8agetab[]. With this we can filter code + * points based on the unicode version in which they were + * defined. The CCC of a non-defined code point is 0. + * leaf[1]: Canonical Combining Class. During normalization, we need + * to do a stable sort into ascending order of all characters + * with a non-zero CCC that occur between two characters with + * a CCC of 0, or at the begin or end of a string. + * The unicode standard guarantees that all CCC values are + * between 0 and 254 inclusive, which leaves 255 available as + * a special value. + * Code points with CCC 0 are known as stoppers. + * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the + * start of a NUL-terminated string that is the decomposition + * of the character. + * The CCC of a decomposable character is the same as the CCC + * of the first character of its decomposition. + * Some characters decompose as the empty string: these are + * characters with the Default_Ignorable_Code_Point property. + * These do affect normalization, as they all have CCC 0. + * + * The decompositions in the trie have been fully expanded. + * + * Casefolding, if applicable, is also done using decompositions. + */ +typedef unsigned char utf8leaf_t; + +#define LEAF_GEN(LEAF) ((LEAF)[0]) +#define LEAF_CCC(LEAF) ((LEAF)[1]) +#define LEAF_STR(LEAF) ((const char*)((LEAF) + 2)) + +#define MAXGEN (255) + +#define MINCCC (0) +#define MAXCCC (254) +#define STOPPER (0) +#define DECOMPOSE (255) +#define HANGUL ((char)(255)) + +#define UTF8HANGULLEAF (12) + +struct tree; +static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *, + const char *, size_t); +static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *); + +unsigned char *utf8data; +size_t utf8data_size; + +utf8trie_t *nfkdi; +utf8trie_t *nfkdicf; + +/* ------------------------------------------------------------------ */ + +/* + * UTF8 valid ranges. + * + * The UTF-8 encoding spreads the bits of a 32bit word over several + * bytes. This table gives the ranges that can be held and how they'd + * be represented. + * + * 0x00000000 0x0000007F: 0xxxxxxx + * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx + * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx + * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx + * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx + * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx + * + * There is an additional requirement on UTF-8, in that only the + * shortest representation of a 32bit value is to be used. A decoder + * must not decode sequences that do not satisfy this requirement. + * Thus the allowed ranges have a lower bound. + * + * 0x00000000 0x0000007F: 0xxxxxxx + * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx + * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx + * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx + * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx + * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx + * + * Actual unicode characters are limited to the range 0x0 - 0x10FFFF, + * 17 planes of 65536 values. This limits the sequences actually seen + * even more, to just the following. + * + * 0 - 0x7f: 0 0x7f + * 0x80 - 0x7ff: 0xc2 0x80 0xdf 0xbf + * 0x800 - 0xffff: 0xe0 0xa0 0x80 0xef 0xbf 0xbf + * 0x10000 - 0x10ffff: 0xf0 0x90 0x80 0x80 0xf4 0x8f 0xbf 0xbf + * + * Even within those ranges not all values are allowed: the surrogates + * 0xd800 - 0xdfff should never be seen. + * + * Note that the longest sequence seen with valid usage is 4 bytes, + * the same a single UTF-32 character. This makes the UTF-8 + * representation of Unicode strictly smaller than UTF-32. + * + * The shortest sequence requirement was introduced by: + * Corrigendum #1: UTF-8 Shortest Form + * It can be found here: + * http://www.unicode.org/versions/corrigendum1.html + * + */ + +#define UTF8_2_BITS 0xC0 +#define UTF8_3_BITS 0xE0 +#define UTF8_4_BITS 0xF0 +#define UTF8_N_BITS 0x80 +#define UTF8_2_MASK 0xE0 +#define UTF8_3_MASK 0xF0 +#define UTF8_4_MASK 0xF8 +#define UTF8_N_MASK 0xC0 +#define UTF8_V_MASK 0x3F +#define UTF8_V_SHIFT 6 + +static int utf8encode(char *str, unsigned int val) +{ + int len; + + if (val < 0x80) { + str[0] = val; + len = 1; + } else if (val < 0x800) { + str[1] = val & UTF8_V_MASK; + str[1] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[0] = val; + str[0] |= UTF8_2_BITS; + len = 2; + } else if (val < 0x10000) { + str[2] = val & UTF8_V_MASK; + str[2] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[1] = val & UTF8_V_MASK; + str[1] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[0] = val; + str[0] |= UTF8_3_BITS; + len = 3; + } else if (val < 0x110000) { + str[3] = val & UTF8_V_MASK; + str[3] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[2] = val & UTF8_V_MASK; + str[2] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[1] = val & UTF8_V_MASK; + str[1] |= UTF8_N_BITS; + val >>= UTF8_V_SHIFT; + str[0] = val; + str[0] |= UTF8_4_BITS; + len = 4; + } else { + printf("%#x: illegal val\n", val); + len = 0; + } + return len; +} + +static unsigned int utf8decode(const char *str) +{ + const unsigned char *s = (const unsigned char*)str; + unsigned int unichar = 0; + + if (*s < 0x80) { + unichar = *s; + } else if (*s < UTF8_3_BITS) { + unichar = *s++ & 0x1F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s & 0x3F; + } else if (*s < UTF8_4_BITS) { + unichar = *s++ & 0x0F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s++ & 0x3F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s & 0x3F; + } else { + unichar = *s++ & 0x0F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s++ & 0x3F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s++ & 0x3F; + unichar <<= UTF8_V_SHIFT; + unichar |= *s & 0x3F; + } + return unichar; +} + +static int utf32valid(unsigned int unichar) +{ + return unichar < 0x110000; +} + +#define HANGUL_SYLLABLE(U) ((U) >= 0xAC00 && (U) <= 0xD7A3) + +#define NODE 1 +#define LEAF 0 + +struct tree { + void *root; + int childnode; + const char *type; + unsigned int maxage; + struct tree *next; + int (*leaf_equal)(void *, void *); + void (*leaf_print)(void *, int); + int (*leaf_mark)(void *); + int (*leaf_size)(void *); + int *(*leaf_index)(struct tree *, void *); + unsigned char *(*leaf_emit)(void *, unsigned char *); + int leafindex[0x110000]; + int index; +}; + +struct node { + int index; + int offset; + int mark; + int size; + struct node *parent; + void *left; + void *right; + unsigned char bitnum; + unsigned char nextbyte; + unsigned char leftnode; + unsigned char rightnode; + unsigned int keybits; + unsigned int keymask; +}; + +/* + * Example lookup function for a tree. + */ +static void *lookup(struct tree *tree, const char *key) +{ + struct node *node; + void *leaf = NULL; + + node = tree->root; + while (!leaf && node) { + if (node->nextbyte) + key++; + if (*key & (1 << (node->bitnum & 7))) { + /* Right leg */ + if (node->rightnode == NODE) { + node = node->right; + } else if (node->rightnode == LEAF) { + leaf = node->right; + } else { + node = NULL; + } + } else { + /* Left leg */ + if (node->leftnode == NODE) { + node = node->left; + } else if (node->leftnode == LEAF) { + leaf = node->left; + } else { + node = NULL; + } + } + } + + return leaf; +} + +/* + * A simple non-recursive tree walker: keep track of visits to the + * left and right branches in the leftmask and rightmask. + */ +static void tree_walk(struct tree *tree) +{ + struct node *node; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + int indent = 1; + int nodes, singletons, leaves; + + nodes = singletons = leaves = 0; + + printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root); + if (tree->childnode == LEAF) { + assert(tree->root); + tree->leaf_print(tree->root, indent); + leaves = 1; + } else { + assert(tree->childnode == NODE); + node = tree->root; + leftmask = rightmask = 0; + while (node) { + printf("%*snode @ %p bitnum %d nextbyte %d" + " left %p right %p mask %x bits %x\n", + indent, "", node, + node->bitnum, node->nextbyte, + node->left, node->right, + node->keymask, node->keybits); + nodes += 1; + if (!(node->left && node->right)) + singletons += 1; + + while (node) { + bitmask = 1 << node->bitnum; + if ((leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + tree->leaf_print(node->left, + indent+1); + leaves += 1; + } else if (node->left) { + assert(node->leftnode == NODE); + indent += 1; + node = node->left; + break; + } + } + if ((rightmask & bitmask) == 0) { + rightmask |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + tree->leaf_print(node->right, + indent+1); + leaves += 1; + } else if (node->right) { + assert(node->rightnode == NODE); + indent += 1; + node = node->right; + break; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + indent -= 1; + } + } + } + printf("nodes %d leaves %d singletons %d\n", + nodes, leaves, singletons); +} + +/* + * Allocate an initialize a new internal node. + */ +static struct node *alloc_node(struct node *parent) +{ + struct node *node; + int bitnum; + + node = malloc(sizeof(*node)); + node->left = node->right = NULL; + node->parent = parent; + node->leftnode = NODE; + node->rightnode = NODE; + node->keybits = 0; + node->keymask = 0; + node->mark = 0; + node->index = 0; + node->offset = -1; + node->size = 4; + + if (node->parent) { + bitnum = parent->bitnum; + if ((bitnum & 7) == 0) { + node->bitnum = bitnum + 7 + 8; + node->nextbyte = 1; + } else { + node->bitnum = bitnum - 1; + node->nextbyte = 0; + } + } else { + node->bitnum = 7; + node->nextbyte = 0; + } + + return node; +} + +/* + * Insert a new leaf into the tree, and collapse any subtrees that are + * fully populated and end in identical leaves. A nextbyte tagged + * internal node will not be removed to preserve the tree's integrity. + * Note that due to the structure of utf8, no nextbyte tagged node + * will be a candidate for removal. + */ +static int insert(struct tree *tree, char *key, int keylen, void *leaf) +{ + struct node *node; + struct node *parent; + void **cursor; + int keybits; + + assert(keylen >= 1 && keylen <= 4); + + node = NULL; + cursor = &tree->root; + keybits = 8 * keylen; + + /* Insert, creating path along the way. */ + while (keybits) { + if (!*cursor) + *cursor = alloc_node(node); + node = *cursor; + if (node->nextbyte) + key++; + if (*key & (1 << (node->bitnum & 7))) + cursor = &node->right; + else + cursor = &node->left; + keybits--; + } + *cursor = leaf; + + /* Merge subtrees if possible. */ + while (node) { + if (*key & (1 << (node->bitnum & 7))) + node->rightnode = LEAF; + else + node->leftnode = LEAF; + if (node->nextbyte) + break; + if (node->leftnode == NODE || node->rightnode == NODE) + break; + assert(node->left); + assert(node->right); + /* Compare */ + if (! tree->leaf_equal(node->left, node->right)) + break; + /* Keep left, drop right leaf. */ + leaf = node->left; + /* Check in parent */ + parent = node->parent; + if (!parent) { + /* root of tree! */ + tree->root = leaf; + tree->childnode = LEAF; + } else if (parent->left == node) { + parent->left = leaf; + parent->leftnode = LEAF; + if (parent->right) { + parent->keymask = 0; + parent->keybits = 0; + } else { + parent->keymask |= (1 << node->bitnum); + } + } else if (parent->right == node) { + parent->right = leaf; + parent->rightnode = LEAF; + if (parent->left) { + parent->keymask = 0; + parent->keybits = 0; + } else { + parent->keymask |= (1 << node->bitnum); + parent->keybits |= (1 << node->bitnum); + } + } else { + /* internal tree error */ + assert(0); + } + free(node); + node = parent; + } + + /* Propagate keymasks up along singleton chains. */ + while (node) { + parent = node->parent; + if (!parent) + break; + /* Nix the mask for parents with two children. */ + if (node->keymask == 0) { + parent->keymask = 0; + parent->keybits = 0; + } else if (parent->left && parent->right) { + parent->keymask = 0; + parent->keybits = 0; + } else { + assert((parent->keymask & node->keymask) == 0); + parent->keymask |= node->keymask; + parent->keymask |= (1 << parent->bitnum); + parent->keybits |= node->keybits; + if (parent->right) + parent->keybits |= (1 << parent->bitnum); + } + node = parent; + } + + return 0; +} + +/* + * Prune internal nodes. + * + * Fully populated subtrees that end at the same leaf have already + * been collapsed. There are still internal nodes that have for both + * their left and right branches a sequence of singletons that make + * identical choices and end in identical leaves. The keymask and + * keybits collected in the nodes describe the choices made in these + * singleton chains. When they are identical for the left and right + * branch of a node, and the two leaves comare identical, the node in + * question can be removed. + * + * Note that nodes with the nextbyte tag set will not be removed by + * this to ensure tree integrity. Note as well that the structure of + * utf8 ensures that these nodes would not have been candidates for + * removal in any case. + */ +static void prune(struct tree *tree) +{ + struct node *node; + struct node *left; + struct node *right; + struct node *parent; + void *leftleaf; + void *rightleaf; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + int count; + + if (verbose > 0) + printf("Pruning %s_%x\n", tree->type, tree->maxage); + + count = 0; + if (tree->childnode == LEAF) + return; + if (!tree->root) + return; + + leftmask = rightmask = 0; + node = tree->root; + while (node) { + if (node->nextbyte) + goto advance; + if (node->leftnode == LEAF) + goto advance; + if (node->rightnode == LEAF) + goto advance; + if (!node->left) + goto advance; + if (!node->right) + goto advance; + left = node->left; + right = node->right; + if (left->keymask == 0) + goto advance; + if (right->keymask == 0) + goto advance; + if (left->keymask != right->keymask) + goto advance; + if (left->keybits != right->keybits) + goto advance; + leftleaf = NULL; + while (!leftleaf) { + assert(left->left || left->right); + if (left->leftnode == LEAF) + leftleaf = left->left; + else if (left->rightnode == LEAF) + leftleaf = left->right; + else if (left->left) + left = left->left; + else if (left->right) + left = left->right; + else + assert(0); + } + rightleaf = NULL; + while (!rightleaf) { + assert(right->left || right->right); + if (right->leftnode == LEAF) + rightleaf = right->left; + else if (right->rightnode == LEAF) + rightleaf = right->right; + else if (right->left) + right = right->left; + else if (right->right) + right = right->right; + else + assert(0); + } + if (! tree->leaf_equal(leftleaf, rightleaf)) + goto advance; + /* + * This node has identical singleton-only subtrees. + * Remove it. + */ + parent = node->parent; + left = node->left; + right = node->right; + if (parent->left == node) + parent->left = left; + else if (parent->right == node) + parent->right = left; + else + assert(0); + left->parent = parent; + left->keymask |= (1 << node->bitnum); + node->left = NULL; + while (node) { + bitmask = 1 << node->bitnum; + leftmask &= ~bitmask; + rightmask &= ~bitmask; + if (node->leftnode == NODE && node->left) { + left = node->left; + free(node); + count++; + node = left; + } else if (node->rightnode == NODE && node->right) { + right = node->right; + free(node); + count++; + node = right; + } else { + node = NULL; + } + } + /* Propagate keymasks up along singleton chains. */ + node = parent; + /* Force re-check */ + bitmask = 1 << node->bitnum; + leftmask &= ~bitmask; + rightmask &= ~bitmask; + for (;;) { + if (node->left && node->right) + break; + if (node->left) { + left = node->left; + node->keymask |= left->keymask; + node->keybits |= left->keybits; + } + if (node->right) { + right = node->right; + node->keymask |= right->keymask; + node->keybits |= right->keybits; + } + node->keymask |= (1 << node->bitnum); + node = node->parent; + /* Force re-check */ + bitmask = 1 << node->bitnum; + leftmask &= ~bitmask; + rightmask &= ~bitmask; + } + advance: + bitmask = 1 << node->bitnum; + if ((leftmask & bitmask) == 0 && + node->leftnode == NODE && + node->left) { + leftmask |= bitmask; + node = node->left; + } else if ((rightmask & bitmask) == 0 && + node->rightnode == NODE && + node->right) { + rightmask |= bitmask; + node = node->right; + } else { + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + } + } + if (verbose > 0) + printf("Pruned %d nodes\n", count); +} + +/* + * Mark the nodes in the tree that lead to leaves that must be + * emitted. + */ +static void mark_nodes(struct tree *tree) +{ + struct node *node; + struct node *n; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + int marked; + + marked = 0; + if (verbose > 0) + printf("Marking %s_%x\n", tree->type, tree->maxage); + if (tree->childnode == LEAF) + goto done; + + assert(tree->childnode == NODE); + node = tree->root; + leftmask = rightmask = 0; + while (node) { + bitmask = 1 << node->bitnum; + if ((leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + if (tree->leaf_mark(node->left)) { + n = node; + while (n && !n->mark) { + marked++; + n->mark = 1; + n = n->parent; + } + } + } else if (node->left) { + assert(node->leftnode == NODE); + node = node->left; + continue; + } + } + if ((rightmask & bitmask) == 0) { + rightmask |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + if (tree->leaf_mark(node->right)) { + n = node; + while (n && !n->mark) { + marked++; + n->mark = 1; + n = n->parent; + } + } + } else if (node->right) { + assert(node->rightnode == NODE); + node = node->right; + continue; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + } + + /* second pass: left siblings and singletons */ + + assert(tree->childnode == NODE); + node = tree->root; + leftmask = rightmask = 0; + while (node) { + bitmask = 1 << node->bitnum; + if ((leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + if (tree->leaf_mark(node->left)) { + n = node; + while (n && !n->mark) { + marked++; + n->mark = 1; + n = n->parent; + } + } + } else if (node->left) { + assert(node->leftnode == NODE); + node = node->left; + if (!node->mark && node->parent->mark) { + marked++; + node->mark = 1; + } + continue; + } + } + if ((rightmask & bitmask) == 0) { + rightmask |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + if (tree->leaf_mark(node->right)) { + n = node; + while (n && !n->mark) { + marked++; + n->mark = 1; + n = n->parent; + } + } + } else if (node->right) { + assert(node->rightnode == NODE); + node = node->right; + if (!node->mark && node->parent->mark && + !node->parent->left) { + marked++; + node->mark = 1; + } + continue; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + } +done: + if (verbose > 0) + printf("Marked %d nodes\n", marked); +} + +/* + * Compute the index of each node and leaf, which is the offset in the + * emitted trie. These values must be pre-computed because relative + * offsets between nodes are used to navigate the tree. + */ +static int index_nodes(struct tree *tree, int index) +{ + struct node *node; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + int count; + int indent; + + /* Align to a cache line (or half a cache line?). */ + while (index % 64) + index++; + tree->index = index; + indent = 1; + count = 0; + + if (verbose > 0) + printf("Indexing %s_%x: %d\n", tree->type, tree->maxage, index); + if (tree->childnode == LEAF) { + index += tree->leaf_size(tree->root); + goto done; + } + + assert(tree->childnode == NODE); + node = tree->root; + leftmask = rightmask = 0; + while (node) { + if (!node->mark) + goto skip; + count++; + if (node->index != index) + node->index = index; + index += node->size; +skip: + while (node) { + bitmask = 1 << node->bitnum; + if (node->mark && (leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + *tree->leaf_index(tree, node->left) = + index; + index += tree->leaf_size(node->left); + count++; + } else if (node->left) { + assert(node->leftnode == NODE); + indent += 1; + node = node->left; + break; + } + } + if (node->mark && (rightmask & bitmask) == 0) { + rightmask |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + *tree->leaf_index(tree, node->right) = index; + index += tree->leaf_size(node->right); + count++; + } else if (node->right) { + assert(node->rightnode == NODE); + indent += 1; + node = node->right; + break; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + indent -= 1; + } + } +done: + /* Round up to a multiple of 16 */ + while (index % 16) + index++; + if (verbose > 0) + printf("Final index %d\n", index); + return index; +} + +/* + * Mark the nodes in a subtree, helper for size_nodes(). + */ +static int mark_subtree(struct node *node) +{ + int changed; + + if (!node || node->mark) + return 0; + node->mark = 1; + node->index = node->parent->index; + changed = 1; + if (node->leftnode == NODE) + changed += mark_subtree(node->left); + if (node->rightnode == NODE) + changed += mark_subtree(node->right); + return changed; +} + +/* + * Compute the size of nodes and leaves. We start by assuming that + * each node needs to store a three-byte offset. The indexes of the + * nodes are calculated based on that, and then this function is + * called to see if the sizes of some nodes can be reduced. This is + * repeated until no more changes are seen. + */ +static int size_nodes(struct tree *tree) +{ + struct tree *next; + struct node *node; + struct node *right; + struct node *n; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + unsigned int pathbits; + unsigned int pathmask; + unsigned int nbit; + int changed; + int offset; + int size; + int indent; + + indent = 1; + changed = 0; + size = 0; + + if (verbose > 0) + printf("Sizing %s_%x\n", tree->type, tree->maxage); + if (tree->childnode == LEAF) + goto done; + + assert(tree->childnode == NODE); + pathbits = 0; + pathmask = 0; + node = tree->root; + leftmask = rightmask = 0; + while (node) { + if (!node->mark) + goto skip; + offset = 0; + if (!node->left || !node->right) { + size = 1; + } else { + if (node->rightnode == NODE) { + /* + * If the right node is not marked, + * look for a corresponding node in + * the next tree. Such a node need + * not exist. + */ + right = node->right; + next = tree->next; + while (!right->mark) { + assert(next); + n = next->root; + while (n->bitnum != node->bitnum) { + nbit = 1 << n->bitnum; + if (!(pathmask & nbit)) + break; + if (pathbits & nbit) { + if (n->rightnode == LEAF) + break; + n = n->right; + } else { + if (n->leftnode == LEAF) + break; + n = n->left; + } + } + if (n->bitnum != node->bitnum) + break; + n = n->right; + right = n; + next = next->next; + } + /* Make sure the right node is marked. */ + if (!right->mark) + changed += mark_subtree(right); + offset = right->index - node->index; + } else { + offset = *tree->leaf_index(tree, node->right); + offset -= node->index; + } + assert(offset >= 0); + assert(offset <= 0xffffff); + if (offset <= 0xff) { + size = 2; + } else if (offset <= 0xffff) { + size = 3; + } else { /* offset <= 0xffffff */ + size = 4; + } + } + if (node->size != size || node->offset != offset) { + node->size = size; + node->offset = offset; + changed++; + } +skip: + while (node) { + bitmask = 1 << node->bitnum; + pathmask |= bitmask; + if (node->mark && (leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + } else if (node->left) { + assert(node->leftnode == NODE); + indent += 1; + node = node->left; + break; + } + } + if (node->mark && (rightmask & bitmask) == 0) { + rightmask |= bitmask; + pathbits |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + } else if (node->right) { + assert(node->rightnode == NODE); + indent += 1; + node = node->right; + break; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + pathmask &= ~bitmask; + pathbits &= ~bitmask; + node = node->parent; + indent -= 1; + } + } +done: + if (verbose > 0) + printf("Found %d changes\n", changed); + return changed; +} + +/* + * Emit a trie for the given tree into the data array. + */ +static void emit(struct tree *tree, unsigned char *data) +{ + struct node *node; + unsigned int leftmask; + unsigned int rightmask; + unsigned int bitmask; + int offlen; + int offset; + int index; + int indent; + int size; + int bytes; + int leaves; + int nodes[4]; + unsigned char byte; + + nodes[0] = nodes[1] = nodes[2] = nodes[3] = 0; + leaves = 0; + bytes = 0; + index = tree->index; + data += index; + indent = 1; + if (verbose > 0) + printf("Emitting %s_%x\n", tree->type, tree->maxage); + if (tree->childnode == LEAF) { + assert(tree->root); + tree->leaf_emit(tree->root, data); + size = tree->leaf_size(tree->root); + index += size; + leaves++; + goto done; + } + + assert(tree->childnode == NODE); + node = tree->root; + leftmask = rightmask = 0; + while (node) { + if (!node->mark) + goto skip; + assert(node->offset != -1); + assert(node->index == index); + + byte = 0; + if (node->nextbyte) + byte |= NEXTBYTE; + byte |= (node->bitnum & BITNUM); + if (node->left && node->right) { + if (node->leftnode == NODE) + byte |= LEFTNODE; + if (node->rightnode == NODE) + byte |= RIGHTNODE; + if (node->offset <= 0xff) + offlen = 1; + else if (node->offset <= 0xffff) + offlen = 2; + else + offlen = 3; + nodes[offlen]++; + offset = node->offset; + byte |= offlen << OFFLEN_SHIFT; + *data++ = byte; + index++; + while (offlen--) { + *data++ = offset & 0xff; + index++; + offset >>= 8; + } + } else if (node->left) { + if (node->leftnode == NODE) + byte |= TRIENODE; + nodes[0]++; + *data++ = byte; + index++; + } else if (node->right) { + byte |= RIGHTNODE; + if (node->rightnode == NODE) + byte |= TRIENODE; + nodes[0]++; + *data++ = byte; + index++; + } else { + assert(0); + } +skip: + while (node) { + bitmask = 1 << node->bitnum; + if (node->mark && (leftmask & bitmask) == 0) { + leftmask |= bitmask; + if (node->leftnode == LEAF) { + assert(node->left); + data = tree->leaf_emit(node->left, + data); + size = tree->leaf_size(node->left); + index += size; + bytes += size; + leaves++; + } else if (node->left) { + assert(node->leftnode == NODE); + indent += 1; + node = node->left; + break; + } + } + if (node->mark && (rightmask & bitmask) == 0) { + rightmask |= bitmask; + if (node->rightnode == LEAF) { + assert(node->right); + data = tree->leaf_emit(node->right, + data); + size = tree->leaf_size(node->right); + index += size; + bytes += size; + leaves++; + } else if (node->right) { + assert(node->rightnode == NODE); + indent += 1; + node = node->right; + break; + } + } + leftmask &= ~bitmask; + rightmask &= ~bitmask; + node = node->parent; + indent -= 1; + } + } +done: + if (verbose > 0) { + printf("Emitted %d (%d) leaves", + leaves, bytes); + printf(" %d (%d+%d+%d+%d) nodes", + nodes[0] + nodes[1] + nodes[2] + nodes[3], + nodes[0], nodes[1], nodes[2], nodes[3]); + printf(" %d total\n", index - tree->index); + } +} + +/* ------------------------------------------------------------------ */ + +/* + * Unicode data. + * + * We need to keep track of the Canonical Combining Class, the Age, + * and decompositions for a code point. + * + * For the Age, we store the index into the ages table. Effectively + * this is a generation number that the table maps to a unicode + * version. + * + * The correction field is used to indicate that this entry is in the + * corrections array, which contains decompositions that were + * corrected in later revisions. The value of the correction field is + * the Unicode version in which the mapping was corrected. + */ +struct unicode_data { + unsigned int code; + int ccc; + int gen; + int correction; + unsigned int *utf32nfkdi; + unsigned int *utf32nfkdicf; + char *utf8nfkdi; + char *utf8nfkdicf; +}; + +struct unicode_data unicode_data[0x110000]; +struct unicode_data *corrections; +int corrections_count; + +struct tree *nfkdi_tree; +struct tree *nfkdicf_tree; + +struct tree *trees; +int trees_count; + +/* + * Check the corrections array to see if this entry was corrected at + * some point. + */ +static struct unicode_data *corrections_lookup(struct unicode_data *u) +{ + int i; + + for (i = 0; i != corrections_count; i++) + if (u->code == corrections[i].code) + return &corrections[i]; + return u; +} + +static int nfkdi_equal(void *l, void *r) +{ + struct unicode_data *left = l; + struct unicode_data *right = r; + + if (left->gen != right->gen) + return 0; + if (left->ccc != right->ccc) + return 0; + if (left->utf8nfkdi && right->utf8nfkdi && + strcmp(left->utf8nfkdi, right->utf8nfkdi) == 0) + return 1; + if (left->utf8nfkdi || right->utf8nfkdi) + return 0; + return 1; +} + +static int nfkdicf_equal(void *l, void *r) +{ + struct unicode_data *left = l; + struct unicode_data *right = r; + + if (left->gen != right->gen) + return 0; + if (left->ccc != right->ccc) + return 0; + if (left->utf8nfkdicf && right->utf8nfkdicf && + strcmp(left->utf8nfkdicf, right->utf8nfkdicf) == 0) + return 1; + if (left->utf8nfkdicf && right->utf8nfkdicf) + return 0; + if (left->utf8nfkdicf || right->utf8nfkdicf) + return 0; + if (left->utf8nfkdi && right->utf8nfkdi && + strcmp(left->utf8nfkdi, right->utf8nfkdi) == 0) + return 1; + if (left->utf8nfkdi || right->utf8nfkdi) + return 0; + return 1; +} + +static void nfkdi_print(void *l, int indent) +{ + struct unicode_data *leaf = l; + + printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf, + leaf->code, leaf->ccc, leaf->gen); + if (leaf->utf8nfkdi && leaf->utf8nfkdi[0] == HANGUL) + printf(" nfkdi \"%s\"", "HANGUL SYLLABLE"); + else if (leaf->utf8nfkdi) + printf(" nfkdi \"%s\"", (const char*)leaf->utf8nfkdi); + printf("\n"); +} + +static void nfkdicf_print(void *l, int indent) +{ + struct unicode_data *leaf = l; + + printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf, + leaf->code, leaf->ccc, leaf->gen); + if (leaf->utf8nfkdicf) + printf(" nfkdicf \"%s\"", (const char*)leaf->utf8nfkdicf); + else if (leaf->utf8nfkdi && leaf->utf8nfkdi[0] == HANGUL) + printf(" nfkdi \"%s\"", "HANGUL SYLLABLE"); + else if (leaf->utf8nfkdi) + printf(" nfkdi \"%s\"", (const char*)leaf->utf8nfkdi); + printf("\n"); +} + +static int nfkdi_mark(void *l) +{ + return 1; +} + +static int nfkdicf_mark(void *l) +{ + struct unicode_data *leaf = l; + + if (leaf->utf8nfkdicf) + return 1; + return 0; +} + +static int correction_mark(void *l) +{ + struct unicode_data *leaf = l; + + return leaf->correction; +} + +static int nfkdi_size(void *l) +{ + struct unicode_data *leaf = l; + + int size = 2; + if (HANGUL_SYLLABLE(leaf->code)) + size += 1; + else if (leaf->utf8nfkdi) + size += strlen(leaf->utf8nfkdi) + 1; + return size; +} + +static int nfkdicf_size(void *l) +{ + struct unicode_data *leaf = l; + + int size = 2; + if (HANGUL_SYLLABLE(leaf->code)) + size += 1; + else if (leaf->utf8nfkdicf) + size += strlen(leaf->utf8nfkdicf) + 1; + else if (leaf->utf8nfkdi) + size += strlen(leaf->utf8nfkdi) + 1; + return size; +} + +static int *nfkdi_index(struct tree *tree, void *l) +{ + struct unicode_data *leaf = l; + + return &tree->leafindex[leaf->code]; +} + +static int *nfkdicf_index(struct tree *tree, void *l) +{ + struct unicode_data *leaf = l; + + return &tree->leafindex[leaf->code]; +} + +static unsigned char *nfkdi_emit(void *l, unsigned char *data) +{ + struct unicode_data *leaf = l; + unsigned char *s; + + *data++ = leaf->gen; + if (HANGUL_SYLLABLE(leaf->code)) { + *data++ = DECOMPOSE; + *data++ = HANGUL; + } else if (leaf->utf8nfkdi) { + *data++ = DECOMPOSE; + s = (unsigned char*)leaf->utf8nfkdi; + while ((*data++ = *s++) != 0) + ; + } else { + *data++ = leaf->ccc; + } + return data; +} + +static unsigned char *nfkdicf_emit(void *l, unsigned char *data) +{ + struct unicode_data *leaf = l; + unsigned char *s; + + *data++ = leaf->gen; + if (HANGUL_SYLLABLE(leaf->code)) { + *data++ = DECOMPOSE; + *data++ = HANGUL; + } else if (leaf->utf8nfkdicf) { + *data++ = DECOMPOSE; + s = (unsigned char*)leaf->utf8nfkdicf; + while ((*data++ = *s++) != 0) + ; + } else if (leaf->utf8nfkdi) { + *data++ = DECOMPOSE; + s = (unsigned char*)leaf->utf8nfkdi; + while ((*data++ = *s++) != 0) + ; + } else { + *data++ = leaf->ccc; + } + return data; +} + +static void utf8_create(struct unicode_data *data) +{ + char utf[18*4+1]; + char *u; + unsigned int *um; + int i; + + if (data->utf8nfkdi) { + assert(data->utf8nfkdi[0] == HANGUL); + return; + } + + u = utf; + um = data->utf32nfkdi; + if (um) { + for (i = 0; um[i]; i++) + u += utf8encode(u, um[i]); + *u = '\0'; + data->utf8nfkdi = strdup(utf); + } + u = utf; + um = data->utf32nfkdicf; + if (um) { + for (i = 0; um[i]; i++) + u += utf8encode(u, um[i]); + *u = '\0'; + if (!data->utf8nfkdi || strcmp(data->utf8nfkdi, utf)) + data->utf8nfkdicf = strdup(utf); + } +} + +static void utf8_init(void) +{ + unsigned int unichar; + int i; + + for (unichar = 0; unichar != 0x110000; unichar++) + utf8_create(&unicode_data[unichar]); + + for (i = 0; i != corrections_count; i++) + utf8_create(&corrections[i]); +} + +static void trees_init(void) +{ + struct unicode_data *data; + unsigned int maxage; + unsigned int nextage; + int count; + int i; + int j; + + /* Count the number of different ages. */ + count = 0; + nextage = (unsigned int)-1; + do { + maxage = nextage; + nextage = 0; + for (i = 0; i <= corrections_count; i++) { + data = &corrections[i]; + if (nextage < data->correction && + data->correction < maxage) + nextage = data->correction; + } + count++; + } while (nextage); + + /* Two trees per age: nfkdi and nfkdicf */ + trees_count = count * 2; + trees = calloc(trees_count, sizeof(struct tree)); + + /* Assign ages to the trees. */ + count = trees_count; + nextage = (unsigned int)-1; + do { + maxage = nextage; + trees[--count].maxage = maxage; + trees[--count].maxage = maxage; + nextage = 0; + for (i = 0; i <= corrections_count; i++) { + data = &corrections[i]; + if (nextage < data->correction && + data->correction < maxage) + nextage = data->correction; + } + } while (nextage); + + /* The ages assigned above are off by one. */ + for (i = 0; i != trees_count; i++) { + j = 0; + while (ages[j] < trees[i].maxage) + j++; + trees[i].maxage = ages[j-1]; + } + + /* Set up the forwarding between trees. */ + trees[trees_count-2].next = &trees[trees_count-1]; + trees[trees_count-1].leaf_mark = nfkdi_mark; + trees[trees_count-2].leaf_mark = nfkdicf_mark; + for (i = 0; i != trees_count-2; i += 2) { + trees[i].next = &trees[trees_count-2]; + trees[i].leaf_mark = correction_mark; + trees[i+1].next = &trees[trees_count-1]; + trees[i+1].leaf_mark = correction_mark; + } + + /* Assign the callouts. */ + for (i = 0; i != trees_count; i += 2) { + trees[i].type = "nfkdicf"; + trees[i].leaf_equal = nfkdicf_equal; + trees[i].leaf_print = nfkdicf_print; + trees[i].leaf_size = nfkdicf_size; + trees[i].leaf_index = nfkdicf_index; + trees[i].leaf_emit = nfkdicf_emit; + + trees[i+1].type = "nfkdi"; + trees[i+1].leaf_equal = nfkdi_equal; + trees[i+1].leaf_print = nfkdi_print; + trees[i+1].leaf_size = nfkdi_size; + trees[i+1].leaf_index = nfkdi_index; + trees[i+1].leaf_emit = nfkdi_emit; + } + + /* Finish init. */ + for (i = 0; i != trees_count; i++) + trees[i].childnode = NODE; +} + +static void trees_populate(void) +{ + struct unicode_data *data; + unsigned int unichar; + char keyval[4]; + int keylen; + int i; + + for (i = 0; i != trees_count; i++) { + if (verbose > 0) { + printf("Populating %s_%x\n", + trees[i].type, trees[i].maxage); + } + for (unichar = 0; unichar != 0x110000; unichar++) { + if (unicode_data[unichar].gen < 0) + continue; + keylen = utf8encode(keyval, unichar); + data = corrections_lookup(&unicode_data[unichar]); + if (data->correction <= trees[i].maxage) + data = &unicode_data[unichar]; + insert(&trees[i], keyval, keylen, data); + } + } +} + +static void trees_reduce(void) +{ + int i; + int size; + int changed; + + for (i = 0; i != trees_count; i++) + prune(&trees[i]); + for (i = 0; i != trees_count; i++) + mark_nodes(&trees[i]); + do { + size = 0; + for (i = 0; i != trees_count; i++) + size = index_nodes(&trees[i], size); + changed = 0; + for (i = 0; i != trees_count; i++) + changed += size_nodes(&trees[i]); + } while (changed); + + utf8data = calloc(size, 1); + utf8data_size = size; + for (i = 0; i != trees_count; i++) + emit(&trees[i], utf8data); + + if (verbose > 0) { + for (i = 0; i != trees_count; i++) { + printf("%s_%x idx %d\n", + trees[i].type, trees[i].maxage, trees[i].index); + } + } + + nfkdi = utf8data + trees[trees_count-1].index; + nfkdicf = utf8data + trees[trees_count-2].index; + + nfkdi_tree = &trees[trees_count-1]; + nfkdicf_tree = &trees[trees_count-2]; +} + +static void verify(struct tree *tree) +{ + struct unicode_data *data; + utf8leaf_t *leaf; + unsigned int unichar; + char key[4]; + unsigned char hangul[UTF8HANGULLEAF]; + int report; + int nocf; + + if (verbose > 0) + printf("Verifying %s_%x\n", tree->type, tree->maxage); + nocf = strcmp(tree->type, "nfkdicf"); + + for (unichar = 0; unichar != 0x110000; unichar++) { + report = 0; + data = corrections_lookup(&unicode_data[unichar]); + if (data->correction <= tree->maxage) + data = &unicode_data[unichar]; + utf8encode(key,unichar); + leaf = utf8lookup(tree, hangul, key); + + if (!leaf) { + if (data->gen != -1) + report++; + if (unichar < 0xd800 || unichar > 0xdfff) + report++; + } else { + if (unichar >= 0xd800 && unichar <= 0xdfff) + report++; + if (data->gen == -1) + report++; + if (data->gen != LEAF_GEN(leaf)) + report++; + if (LEAF_CCC(leaf) == DECOMPOSE) { + if (HANGUL_SYLLABLE(data->code)) { + if (data->utf8nfkdi[0] != HANGUL) + report++; + } else if (nocf) { + if (!data->utf8nfkdi) { + report++; + } else if (strcmp(data->utf8nfkdi, + LEAF_STR(leaf))) { + report++; + } + } else { + if (!data->utf8nfkdicf && + !data->utf8nfkdi) { + report++; + } else if (data->utf8nfkdicf) { + if (strcmp(data->utf8nfkdicf, + LEAF_STR(leaf))) + report++; + } else if (strcmp(data->utf8nfkdi, + LEAF_STR(leaf))) { + report++; + } + } + } else if (data->ccc != LEAF_CCC(leaf)) { + report++; + } + } + if (report) { + printf("%X code %X gen %d ccc %d" + " nfkdi -> \"%s\"", + unichar, data->code, data->gen, + data->ccc, + data->utf8nfkdi); + if (leaf) { + printf(" gen %d ccc %d" + " nfkdi -> \"%s\"", + LEAF_GEN(leaf), + LEAF_CCC(leaf), + LEAF_CCC(leaf) == DECOMPOSE ? + LEAF_STR(leaf) : ""); + } + printf("\n"); + } + } +} + +static void trees_verify(void) +{ + int i; + + for (i = 0; i != trees_count; i++) + verify(&trees[i]); +} + +/* ------------------------------------------------------------------ */ + +static void help(void) +{ + printf("Usage: %s [options]\n", argv0); + printf("\n"); + printf("This program creates an a data trie used for parsing and\n"); + printf("normalization of UTF-8 strings. The trie is derived from\n"); + printf("a set of input files from the Unicode character database\n"); + printf("found at: http://www.unicode.org/Public/UCD/latest/ucd/\n"); + printf("\n"); + printf("The generated tree supports two normalization forms:\n"); + printf("\n"); + printf("\tnfkdi:\n"); + printf("\t- Apply unicode normalization form NFKD.\n"); + printf("\t- Remove any Default_Ignorable_Code_Point.\n"); + printf("\n"); + printf("\tnfkdicf:\n"); + printf("\t- Apply unicode normalization form NFKD.\n"); + printf("\t- Remove any Default_Ignorable_Code_Point.\n"); + printf("\t- Apply a full casefold (C + F).\n"); + printf("\n"); + printf("These forms were chosen as being most useful when dealing\n"); + printf("with file names: NFKD catches most cases where characters\n"); + printf("should be considered equivalent. The ignorables are mostly\n"); + printf("invisible, making names hard to type.\n"); + printf("\n"); + printf("The options to specify the files to be used are listed\n"); + printf("below with their default values, which are the names used\n"); + printf("by version 11.0.0 of the Unicode Character Database.\n"); + printf("\n"); + printf("The input files:\n"); + printf("\t-a %s\n", AGE_NAME); + printf("\t-c %s\n", CCC_NAME); + printf("\t-p %s\n", PROP_NAME); + printf("\t-d %s\n", DATA_NAME); + printf("\t-f %s\n", FOLD_NAME); + printf("\t-n %s\n", NORM_NAME); + printf("\n"); + printf("Additionally, the generated tables are tested using:\n"); + printf("\t-t %s\n", TEST_NAME); + printf("\n"); + printf("Finally, the output file:\n"); + printf("\t-o %s\n", UTF8_NAME); + printf("\n"); +} + +static void usage(void) +{ + help(); + exit(1); +} + +static void open_fail(const char *name, int error) +{ + printf("Error %d opening %s: %s\n", error, name, strerror(error)); + exit(1); +} + +static void file_fail(const char *filename) +{ + printf("Error parsing %s\n", filename); + exit(1); +} + +static void line_fail(const char *filename, const char *line) +{ + printf("Error parsing %s:%s\n", filename, line); + exit(1); +} + +/* ------------------------------------------------------------------ */ + +static void print_utf32(unsigned int *utf32str) +{ + int i; + + for (i = 0; utf32str[i]; i++) + printf(" %X", utf32str[i]); +} + +static void print_utf32nfkdi(unsigned int unichar) +{ + printf(" %X ->", unichar); + print_utf32(unicode_data[unichar].utf32nfkdi); + printf("\n"); +} + +static void print_utf32nfkdicf(unsigned int unichar) +{ + printf(" %X ->", unichar); + print_utf32(unicode_data[unichar].utf32nfkdicf); + printf("\n"); +} + +/* ------------------------------------------------------------------ */ + +static void age_init(void) +{ + FILE *file; + unsigned int first; + unsigned int last; + unsigned int unichar; + unsigned int major; + unsigned int minor; + unsigned int revision; + int gen; + int count; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", age_name); + + file = fopen(age_name, "r"); + if (!file) + open_fail(age_name, errno); + count = 0; + + gen = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "# Age=V%d_%d_%d", + &major, &minor, &revision); + if (ret == 3) { + ages_count++; + if (verbose > 1) + printf(" Age V%d_%d_%d\n", + major, minor, revision); + if (!age_valid(major, minor, revision)) + line_fail(age_name, line); + continue; + } + ret = sscanf(line, "# Age=V%d_%d", &major, &minor); + if (ret == 2) { + ages_count++; + if (verbose > 1) + printf(" Age V%d_%d\n", major, minor); + if (!age_valid(major, minor, 0)) + line_fail(age_name, line); + continue; + } + } + + /* We must have found something above. */ + if (verbose > 1) + printf("%d age entries\n", ages_count); + if (ages_count == 0 || ages_count > MAXGEN) + file_fail(age_name); + + /* There is a 0 entry. */ + ages_count++; + ages = calloc(ages_count + 1, sizeof(*ages)); + /* And a guard entry. */ + ages[ages_count] = (unsigned int)-1; + + rewind(file); + count = 0; + gen = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "# Age=V%d_%d_%d", + &major, &minor, &revision); + if (ret == 3) { + ages[++gen] = + UNICODE_AGE(major, minor, revision); + if (verbose > 1) + printf(" Age V%d_%d_%d = gen %d\n", + major, minor, revision, gen); + if (!age_valid(major, minor, revision)) + line_fail(age_name, line); + continue; + } + ret = sscanf(line, "# Age=V%d_%d", &major, &minor); + if (ret == 2) { + ages[++gen] = UNICODE_AGE(major, minor, 0); + if (verbose > 1) + printf(" Age V%d_%d = %d\n", + major, minor, gen); + if (!age_valid(major, minor, 0)) + line_fail(age_name, line); + continue; + } + ret = sscanf(line, "%X..%X ; %d.%d #", + &first, &last, &major, &minor); + if (ret == 4) { + for (unichar = first; unichar <= last; unichar++) + unicode_data[unichar].gen = gen; + count += 1 + last - first; + if (verbose > 1) + printf(" %X..%X gen %d\n", first, last, gen); + if (!utf32valid(first) || !utf32valid(last)) + line_fail(age_name, line); + continue; + } + ret = sscanf(line, "%X ; %d.%d #", &unichar, &major, &minor); + if (ret == 3) { + unicode_data[unichar].gen = gen; + count++; + if (verbose > 1) + printf(" %X gen %d\n", unichar, gen); + if (!utf32valid(unichar)) + line_fail(age_name, line); + continue; + } + } + unicode_maxage = ages[gen]; + fclose(file); + + /* Nix surrogate block */ + if (verbose > 1) + printf(" Removing surrogate block D800..DFFF\n"); + for (unichar = 0xd800; unichar <= 0xdfff; unichar++) + unicode_data[unichar].gen = -1; + + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(age_name); +} + +static void ccc_init(void) +{ + FILE *file; + unsigned int first; + unsigned int last; + unsigned int unichar; + unsigned int value; + int count; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", ccc_name); + + file = fopen(ccc_name, "r"); + if (!file) + open_fail(ccc_name, errno); + + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X..%X ; %d #", &first, &last, &value); + if (ret == 3) { + for (unichar = first; unichar <= last; unichar++) { + unicode_data[unichar].ccc = value; + count++; + } + if (verbose > 1) + printf(" %X..%X ccc %d\n", first, last, value); + if (!utf32valid(first) || !utf32valid(last)) + line_fail(ccc_name, line); + continue; + } + ret = sscanf(line, "%X ; %d #", &unichar, &value); + if (ret == 2) { + unicode_data[unichar].ccc = value; + count++; + if (verbose > 1) + printf(" %X ccc %d\n", unichar, value); + if (!utf32valid(unichar)) + line_fail(ccc_name, line); + continue; + } + } + fclose(file); + + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(ccc_name); +} + +static void nfkdi_init(void) +{ + FILE *file; + unsigned int unichar; + unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */ + char *s; + unsigned int *um; + int count; + int i; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", data_name); + file = fopen(data_name, "r"); + if (!file) + open_fail(data_name, errno); + + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X;%*[^;];%*[^;];%*[^;];%*[^;];%[^;];", + &unichar, buf0); + if (ret != 2) + continue; + if (!utf32valid(unichar)) + line_fail(data_name, line); + + s = buf0; + /* skip over */ + if (*s == '<') + while (*s++ != ' ') + ; + /* decode the decomposition into UTF-32 */ + i = 0; + while (*s) { + mapping[i] = strtoul(s, &s, 16); + if (!utf32valid(mapping[i])) + line_fail(data_name, line); + i++; + } + mapping[i++] = 0; + + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdi = um; + + if (verbose > 1) + print_utf32nfkdi(unichar); + count++; + } + fclose(file); + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(data_name); +} + +static void nfkdicf_init(void) +{ + FILE *file; + unsigned int unichar; + unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */ + char status; + char *s; + unsigned int *um; + int i; + int count; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", fold_name); + file = fopen(fold_name, "r"); + if (!file) + open_fail(fold_name, errno); + + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X; %c; %[^;];", &unichar, &status, buf0); + if (ret != 3) + continue; + if (!utf32valid(unichar)) + line_fail(fold_name, line); + /* Use the C+F casefold. */ + if (status != 'C' && status != 'F') + continue; + s = buf0; + if (*s == '<') + while (*s++ != ' ') + ; + i = 0; + while (*s) { + mapping[i] = strtoul(s, &s, 16); + if (!utf32valid(mapping[i])) + line_fail(fold_name, line); + i++; + } + mapping[i++] = 0; + + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdicf = um; + + if (verbose > 1) + print_utf32nfkdicf(unichar); + count++; + } + fclose(file); + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(fold_name); +} + +static void ignore_init(void) +{ + FILE *file; + unsigned int unichar; + unsigned int first; + unsigned int last; + unsigned int *um; + int count; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", prop_name); + file = fopen(prop_name, "r"); + if (!file) + open_fail(prop_name, errno); + assert(file); + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X..%X ; %s # ", &first, &last, buf0); + if (ret == 3) { + if (strcmp(buf0, "Default_Ignorable_Code_Point")) + continue; + if (!utf32valid(first) || !utf32valid(last)) + line_fail(prop_name, line); + for (unichar = first; unichar <= last; unichar++) { + free(unicode_data[unichar].utf32nfkdi); + um = malloc(sizeof(unsigned int)); + *um = 0; + unicode_data[unichar].utf32nfkdi = um; + free(unicode_data[unichar].utf32nfkdicf); + um = malloc(sizeof(unsigned int)); + *um = 0; + unicode_data[unichar].utf32nfkdicf = um; + count++; + } + if (verbose > 1) + printf(" %X..%X Default_Ignorable_Code_Point\n", + first, last); + continue; + } + ret = sscanf(line, "%X ; %s # ", &unichar, buf0); + if (ret == 2) { + if (strcmp(buf0, "Default_Ignorable_Code_Point")) + continue; + if (!utf32valid(unichar)) + line_fail(prop_name, line); + free(unicode_data[unichar].utf32nfkdi); + um = malloc(sizeof(unsigned int)); + *um = 0; + unicode_data[unichar].utf32nfkdi = um; + free(unicode_data[unichar].utf32nfkdicf); + um = malloc(sizeof(unsigned int)); + *um = 0; + unicode_data[unichar].utf32nfkdicf = um; + if (verbose > 1) + printf(" %X Default_Ignorable_Code_Point\n", + unichar); + count++; + continue; + } + } + fclose(file); + + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(prop_name); +} + +static void corrections_init(void) +{ + FILE *file; + unsigned int unichar; + unsigned int major; + unsigned int minor; + unsigned int revision; + unsigned int age; + unsigned int *um; + unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */ + char *s; + int i; + int count; + int ret; + + if (verbose > 0) + printf("Parsing %s\n", norm_name); + file = fopen(norm_name, "r"); + if (!file) + open_fail(norm_name, errno); + + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #", + &unichar, buf0, buf1, + &major, &minor, &revision); + if (ret != 6) + continue; + if (!utf32valid(unichar) || !age_valid(major, minor, revision)) + line_fail(norm_name, line); + count++; + } + corrections = calloc(count, sizeof(struct unicode_data)); + corrections_count = count; + rewind(file); + + count = 0; + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #", + &unichar, buf0, buf1, + &major, &minor, &revision); + if (ret != 6) + continue; + if (!utf32valid(unichar) || !age_valid(major, minor, revision)) + line_fail(norm_name, line); + corrections[count] = unicode_data[unichar]; + assert(corrections[count].code == unichar); + age = UNICODE_AGE(major, minor, revision); + corrections[count].correction = age; + + i = 0; + s = buf0; + while (*s) { + mapping[i] = strtoul(s, &s, 16); + if (!utf32valid(mapping[i])) + line_fail(norm_name, line); + i++; + } + mapping[i++] = 0; + + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + corrections[count].utf32nfkdi = um; + + if (verbose > 1) + printf(" %X -> %s -> %s V%d_%d_%d\n", + unichar, buf0, buf1, major, minor, revision); + count++; + } + fclose(file); + + if (verbose > 0) + printf("Found %d entries\n", count); + if (count == 0) + file_fail(norm_name); +} + +/* ------------------------------------------------------------------ */ + +/* + * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0) + * + * AC00;;Lo;0;L;;;;;N;;;;; + * D7A3;;Lo;0;L;;;;;N;;;;; + * + * SBase = 0xAC00 + * LBase = 0x1100 + * VBase = 0x1161 + * TBase = 0x11A7 + * LCount = 19 + * VCount = 21 + * TCount = 28 + * NCount = 588 (VCount * TCount) + * SCount = 11172 (LCount * NCount) + * + * Decomposition: + * SIndex = s - SBase + * + * LV (Canonical/Full) + * LIndex = SIndex / NCount + * VIndex = (Sindex % NCount) / TCount + * LPart = LBase + LIndex + * VPart = VBase + VIndex + * + * LVT (Canonical) + * LVIndex = (SIndex / TCount) * TCount + * TIndex = (Sindex % TCount) + * LVPart = SBase + LVIndex + * TPart = TBase + TIndex + * + * LVT (Full) + * LIndex = SIndex / NCount + * VIndex = (Sindex % NCount) / TCount + * TIndex = (Sindex % TCount) + * LPart = LBase + LIndex + * VPart = VBase + VIndex + * if (TIndex == 0) { + * d = + * } else { + * TPart = TBase + TIndex + * d = + * } + * + */ + +static void hangul_decompose(void) +{ + unsigned int sb = 0xAC00; + unsigned int lb = 0x1100; + unsigned int vb = 0x1161; + unsigned int tb = 0x11a7; + /* unsigned int lc = 19; */ + unsigned int vc = 21; + unsigned int tc = 28; + unsigned int nc = (vc * tc); + /* unsigned int sc = (lc * nc); */ + unsigned int unichar; + unsigned int mapping[4]; + unsigned int *um; + int count; + int i; + + if (verbose > 0) + printf("Decomposing hangul\n"); + /* Hangul */ + count = 0; + for (unichar = 0xAC00; unichar <= 0xD7A3; unichar++) { + unsigned int si = unichar - sb; + unsigned int li = si / nc; + unsigned int vi = (si % nc) / tc; + unsigned int ti = si % tc; + + i = 0; + mapping[i++] = lb + li; + mapping[i++] = vb + vi; + if (ti) + mapping[i++] = tb + ti; + mapping[i++] = 0; + + assert(!unicode_data[unichar].utf32nfkdi); + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdi = um; + + assert(!unicode_data[unichar].utf32nfkdicf); + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdicf = um; + + /* + * Add a cookie as a reminder that the hangul syllable + * decompositions must not be stored in the generated + * trie. + */ + unicode_data[unichar].utf8nfkdi = malloc(2); + unicode_data[unichar].utf8nfkdi[0] = HANGUL; + unicode_data[unichar].utf8nfkdi[1] = '\0'; + + if (verbose > 1) + print_utf32nfkdi(unichar); + + count++; + } + if (verbose > 0) + printf("Created %d entries\n", count); +} + +static void nfkdi_decompose(void) +{ + unsigned int unichar; + unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */ + unsigned int *um; + unsigned int *dc; + int count; + int i; + int j; + int ret; + + if (verbose > 0) + printf("Decomposing nfkdi\n"); + + count = 0; + for (unichar = 0; unichar != 0x110000; unichar++) { + if (!unicode_data[unichar].utf32nfkdi) + continue; + for (;;) { + ret = 1; + i = 0; + um = unicode_data[unichar].utf32nfkdi; + while (*um) { + dc = unicode_data[*um].utf32nfkdi; + if (dc) { + for (j = 0; dc[j]; j++) + mapping[i++] = dc[j]; + ret = 0; + } else { + mapping[i++] = *um; + } + um++; + } + mapping[i++] = 0; + if (ret) + break; + free(unicode_data[unichar].utf32nfkdi); + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdi = um; + } + /* Add this decomposition to nfkdicf if there is no entry. */ + if (!unicode_data[unichar].utf32nfkdicf) { + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdicf = um; + } + if (verbose > 1) + print_utf32nfkdi(unichar); + count++; + } + if (verbose > 0) + printf("Processed %d entries\n", count); +} + +static void nfkdicf_decompose(void) +{ + unsigned int unichar; + unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */ + unsigned int *um; + unsigned int *dc; + int count; + int i; + int j; + int ret; + + if (verbose > 0) + printf("Decomposing nfkdicf\n"); + count = 0; + for (unichar = 0; unichar != 0x110000; unichar++) { + if (!unicode_data[unichar].utf32nfkdicf) + continue; + for (;;) { + ret = 1; + i = 0; + um = unicode_data[unichar].utf32nfkdicf; + while (*um) { + dc = unicode_data[*um].utf32nfkdicf; + if (dc) { + for (j = 0; dc[j]; j++) + mapping[i++] = dc[j]; + ret = 0; + } else { + mapping[i++] = *um; + } + um++; + } + mapping[i++] = 0; + if (ret) + break; + free(unicode_data[unichar].utf32nfkdicf); + um = malloc(i * sizeof(unsigned int)); + memcpy(um, mapping, i * sizeof(unsigned int)); + unicode_data[unichar].utf32nfkdicf = um; + } + if (verbose > 1) + print_utf32nfkdicf(unichar); + count++; + } + if (verbose > 0) + printf("Processed %d entries\n", count); +} + +/* ------------------------------------------------------------------ */ + +int utf8agemax(struct tree *, const char *); +int utf8nagemax(struct tree *, const char *, size_t); +int utf8agemin(struct tree *, const char *); +int utf8nagemin(struct tree *, const char *, size_t); +ssize_t utf8len(struct tree *, const char *); +ssize_t utf8nlen(struct tree *, const char *, size_t); +struct utf8cursor; +int utf8cursor(struct utf8cursor *, struct tree *, const char *); +int utf8ncursor(struct utf8cursor *, struct tree *, const char *, size_t); +int utf8byte(struct utf8cursor *); + +/* + * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0) + * + * AC00;;Lo;0;L;;;;;N;;;;; + * D7A3;;Lo;0;L;;;;;N;;;;; + * + * SBase = 0xAC00 + * LBase = 0x1100 + * VBase = 0x1161 + * TBase = 0x11A7 + * LCount = 19 + * VCount = 21 + * TCount = 28 + * NCount = 588 (VCount * TCount) + * SCount = 11172 (LCount * NCount) + * + * Decomposition: + * SIndex = s - SBase + * + * LV (Canonical/Full) + * LIndex = SIndex / NCount + * VIndex = (Sindex % NCount) / TCount + * LPart = LBase + LIndex + * VPart = VBase + VIndex + * + * LVT (Canonical) + * LVIndex = (SIndex / TCount) * TCount + * TIndex = (Sindex % TCount) + * LVPart = SBase + LVIndex + * TPart = TBase + TIndex + * + * LVT (Full) + * LIndex = SIndex / NCount + * VIndex = (Sindex % NCount) / TCount + * TIndex = (Sindex % TCount) + * LPart = LBase + LIndex + * VPart = VBase + VIndex + * if (TIndex == 0) { + * d = + * } else { + * TPart = TBase + TIndex + * d = + * } + */ + +/* Constants */ +#define SB (0xAC00) +#define LB (0x1100) +#define VB (0x1161) +#define TB (0x11A7) +#define LC (19) +#define VC (21) +#define TC (28) +#define NC (VC * TC) +#define SC (LC * NC) + +/* Algorithmic decomposition of hangul syllable. */ +static utf8leaf_t *utf8hangul(const char *str, unsigned char *hangul) +{ + unsigned int si; + unsigned int li; + unsigned int vi; + unsigned int ti; + unsigned char *h; + + /* Calculate the SI, LI, VI, and TI values. */ + si = utf8decode(str) - SB; + li = si / NC; + vi = (si % NC) / TC; + ti = si % TC; + + /* Fill in base of leaf. */ + h = hangul; + LEAF_GEN(h) = 2; + LEAF_CCC(h) = DECOMPOSE; + h += 2; + + /* Add LPart, a 3-byte UTF-8 sequence. */ + h += utf8encode((char *)h, li + LB); + + /* Add VPart, a 3-byte UTF-8 sequence. */ + h += utf8encode((char *)h, vi + VB); + + /* Add TPart if required, also a 3-byte UTF-8 sequence. */ + if (ti) + h += utf8encode((char *)h, ti + TB); + + /* Terminate string. */ + h[0] = '\0'; + + return hangul; +} + +/* + * Use trie to scan s, touching at most len bytes. + * Returns the leaf if one exists, NULL otherwise. + * + * A non-NULL return guarantees that the UTF-8 sequence starting at s + * is well-formed and corresponds to a known unicode code point. The + * shorthand for this will be "is valid UTF-8 unicode". + */ +static utf8leaf_t *utf8nlookup(struct tree *tree, unsigned char *hangul, + const char *s, size_t len) +{ + utf8trie_t *trie = utf8data + tree->index; + int offlen; + int offset; + int mask; + int node; + + if (!tree) + return NULL; + if (len == 0) + return NULL; + node = 1; + while (node) { + offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT; + if (*trie & NEXTBYTE) { + if (--len == 0) + return NULL; + s++; + } + mask = 1 << (*trie & BITNUM); + if (*s & mask) { + /* Right leg */ + if (offlen) { + /* Right node at offset of trie */ + node = (*trie & RIGHTNODE); + offset = trie[offlen]; + while (--offlen) { + offset <<= 8; + offset |= trie[offlen]; + } + trie += offset; + } else if (*trie & RIGHTPATH) { + /* Right node after this node */ + node = (*trie & TRIENODE); + trie++; + } else { + /* No right node. */ + return NULL; + } + } else { + /* Left leg */ + if (offlen) { + /* Left node after this node. */ + node = (*trie & LEFTNODE); + trie += offlen + 1; + } else if (*trie & RIGHTPATH) { + /* No left node. */ + return NULL; + } else { + /* Left node after this node */ + node = (*trie & TRIENODE); + trie++; + } + } + } + /* + * Hangul decomposition is done algorithmically. These are the + * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is + * always 3 bytes long, so s has been advanced twice, and the + * start of the sequence is at s-2. + */ + if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL) + trie = utf8hangul(s - 2, hangul); + return trie; +} + +/* + * Use trie to scan s. + * Returns the leaf if one exists, NULL otherwise. + * + * Forwards to trie_nlookup(). + */ +static utf8leaf_t *utf8lookup(struct tree *tree, unsigned char *hangul, + const char *s) +{ + return utf8nlookup(tree, hangul, s, (size_t)-1); +} + +/* + * Return the number of bytes used by the current UTF-8 sequence. + * Assumes the input points to the first byte of a valid UTF-8 + * sequence. + */ +static inline int utf8clen(const char *s) +{ + unsigned char c = *s; + return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0); +} + +/* + * Maximum age of any character in s. + * Return -1 if s is not valid UTF-8 unicode. + * Return 0 if only non-assigned code points are used. + */ +int utf8agemax(struct tree *tree, const char *s) +{ + utf8leaf_t *leaf; + int age = 0; + int leaf_age; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + + while (*s) { + leaf = utf8lookup(tree, hangul, s); + if (!leaf) + return -1; + leaf_age = ages[LEAF_GEN(leaf)]; + if (leaf_age <= tree->maxage && leaf_age > age) + age = leaf_age; + s += utf8clen(s); + } + return age; +} + +/* + * Minimum age of any character in s. + * Return -1 if s is not valid UTF-8 unicode. + * Return 0 if non-assigned code points are used. + */ +int utf8agemin(struct tree *tree, const char *s) +{ + utf8leaf_t *leaf; + int age; + int leaf_age; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + age = tree->maxage; + while (*s) { + leaf = utf8lookup(tree, hangul, s); + if (!leaf) + return -1; + leaf_age = ages[LEAF_GEN(leaf)]; + if (leaf_age <= tree->maxage && leaf_age < age) + age = leaf_age; + s += utf8clen(s); + } + return age; +} + +/* + * Maximum age of any character in s, touch at most len bytes. + * Return -1 if s is not valid UTF-8 unicode. + */ +int utf8nagemax(struct tree *tree, const char *s, size_t len) +{ + utf8leaf_t *leaf; + int age = 0; + int leaf_age; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + + while (len && *s) { + leaf = utf8nlookup(tree, hangul, s, len); + if (!leaf) + return -1; + leaf_age = ages[LEAF_GEN(leaf)]; + if (leaf_age <= tree->maxage && leaf_age > age) + age = leaf_age; + len -= utf8clen(s); + s += utf8clen(s); + } + return age; +} + +/* + * Maximum age of any character in s, touch at most len bytes. + * Return -1 if s is not valid UTF-8 unicode. + */ +int utf8nagemin(struct tree *tree, const char *s, size_t len) +{ + utf8leaf_t *leaf; + int leaf_age; + int age; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + age = tree->maxage; + while (len && *s) { + leaf = utf8nlookup(tree, hangul, s, len); + if (!leaf) + return -1; + leaf_age = ages[LEAF_GEN(leaf)]; + if (leaf_age <= tree->maxage && leaf_age < age) + age = leaf_age; + len -= utf8clen(s); + s += utf8clen(s); + } + return age; +} + +/* + * Length of the normalization of s. + * Return -1 if s is not valid UTF-8 unicode. + * + * A string of Default_Ignorable_Code_Point has length 0. + */ +ssize_t utf8len(struct tree *tree, const char *s) +{ + utf8leaf_t *leaf; + size_t ret = 0; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + while (*s) { + leaf = utf8lookup(tree, hangul, s); + if (!leaf) + return -1; + if (ages[LEAF_GEN(leaf)] > tree->maxage) + ret += utf8clen(s); + else if (LEAF_CCC(leaf) == DECOMPOSE) + ret += strlen(LEAF_STR(leaf)); + else + ret += utf8clen(s); + s += utf8clen(s); + } + return ret; +} + +/* + * Length of the normalization of s, touch at most len bytes. + * Return -1 if s is not valid UTF-8 unicode. + */ +ssize_t utf8nlen(struct tree *tree, const char *s, size_t len) +{ + utf8leaf_t *leaf; + size_t ret = 0; + unsigned char hangul[UTF8HANGULLEAF]; + + if (!tree) + return -1; + while (len && *s) { + leaf = utf8nlookup(tree, hangul, s, len); + if (!leaf) + return -1; + if (ages[LEAF_GEN(leaf)] > tree->maxage) + ret += utf8clen(s); + else if (LEAF_CCC(leaf) == DECOMPOSE) + ret += strlen(LEAF_STR(leaf)); + else + ret += utf8clen(s); + len -= utf8clen(s); + s += utf8clen(s); + } + return ret; +} + +/* + * Cursor structure used by the normalizer. + */ +struct utf8cursor { + struct tree *tree; + const char *s; + const char *p; + const char *ss; + const char *sp; + unsigned int len; + unsigned int slen; + short int ccc; + short int nccc; + unsigned int unichar; + unsigned char hangul[UTF8HANGULLEAF]; +}; + +/* + * Set up an utf8cursor for use by utf8byte(). + * + * s : string. + * len : length of s. + * u8c : pointer to cursor. + * trie : utf8trie_t to use for normalization. + * + * Returns -1 on error, 0 on success. + */ +int utf8ncursor(struct utf8cursor *u8c, struct tree *tree, const char *s, + size_t len) +{ + if (!tree) + return -1; + if (!s) + return -1; + u8c->tree = tree; + u8c->s = s; + u8c->p = NULL; + u8c->ss = NULL; + u8c->sp = NULL; + u8c->len = len; + u8c->slen = 0; + u8c->ccc = STOPPER; + u8c->nccc = STOPPER; + u8c->unichar = 0; + /* Check we didn't clobber the maximum length. */ + if (u8c->len != len) + return -1; + /* The first byte of s may not be an utf8 continuation. */ + if (len > 0 && (*s & 0xC0) == 0x80) + return -1; + return 0; +} + +/* + * Set up an utf8cursor for use by utf8byte(). + * + * s : NUL-terminated string. + * u8c : pointer to cursor. + * trie : utf8trie_t to use for normalization. + * + * Returns -1 on error, 0 on success. + */ +int utf8cursor(struct utf8cursor *u8c, struct tree *tree, const char *s) +{ + return utf8ncursor(u8c, tree, s, (unsigned int)-1); +} + +/* + * Get one byte from the normalized form of the string described by u8c. + * + * Returns the byte cast to an unsigned char on success, and -1 on failure. + * + * The cursor keeps track of the location in the string in u8c->s. + * When a character is decomposed, the current location is stored in + * u8c->p, and u8c->s is set to the start of the decomposition. Note + * that bytes from a decomposition do not count against u8c->len. + * + * Characters are emitted if they match the current CCC in u8c->ccc. + * Hitting end-of-string while u8c->ccc == STOPPER means we're done, + * and the function returns 0 in that case. + * + * Sorting by CCC is done by repeatedly scanning the string. The + * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at + * the start of the scan. The first pass finds the lowest CCC to be + * emitted and stores it in u8c->nccc, the second pass emits the + * characters with this CCC and finds the next lowest CCC. This limits + * the number of passes to 1 + the number of different CCCs in the + * sequence being scanned. + * + * Therefore: + * u8c->p != NULL -> a decomposition is being scanned. + * u8c->ss != NULL -> this is a repeating scan. + * u8c->ccc == -1 -> this is the first scan of a repeating scan. + */ +int utf8byte(struct utf8cursor *u8c) +{ + utf8leaf_t *leaf; + int ccc; + + for (;;) { + /* Check for the end of a decomposed character. */ + if (u8c->p && *u8c->s == '\0') { + u8c->s = u8c->p; + u8c->p = NULL; + } + + /* Check for end-of-string. */ + if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) { + /* There is no next byte. */ + if (u8c->ccc == STOPPER) + return 0; + /* End-of-string during a scan counts as a stopper. */ + ccc = STOPPER; + goto ccc_mismatch; + } else if ((*u8c->s & 0xC0) == 0x80) { + /* This is a continuation of the current character. */ + if (!u8c->p) + u8c->len--; + return (unsigned char)*u8c->s++; + } + + /* Look up the data for the current character. */ + if (u8c->p) { + leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s); + } else { + leaf = utf8nlookup(u8c->tree, u8c->hangul, + u8c->s, u8c->len); + } + + /* No leaf found implies that the input is a binary blob. */ + if (!leaf) + return -1; + + /* Characters that are too new have CCC 0. */ + if (ages[LEAF_GEN(leaf)] > u8c->tree->maxage) { + ccc = STOPPER; + } else if ((ccc = LEAF_CCC(leaf)) == DECOMPOSE) { + u8c->len -= utf8clen(u8c->s); + u8c->p = u8c->s + utf8clen(u8c->s); + u8c->s = LEAF_STR(leaf); + /* Empty decomposition implies CCC 0. */ + if (*u8c->s == '\0') { + if (u8c->ccc == STOPPER) + continue; + ccc = STOPPER; + goto ccc_mismatch; + } + leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s); + ccc = LEAF_CCC(leaf); + } + u8c->unichar = utf8decode(u8c->s); + + /* + * If this is not a stopper, then see if it updates + * the next canonical class to be emitted. + */ + if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc) + u8c->nccc = ccc; + + /* + * Return the current byte if this is the current + * combining class. + */ + if (ccc == u8c->ccc) { + if (!u8c->p) + u8c->len--; + return (unsigned char)*u8c->s++; + } + + /* Current combining class mismatch. */ + ccc_mismatch: + if (u8c->nccc == STOPPER) { + /* + * Scan forward for the first canonical class + * to be emitted. Save the position from + * which to restart. + */ + assert(u8c->ccc == STOPPER); + u8c->ccc = MINCCC - 1; + u8c->nccc = ccc; + u8c->sp = u8c->p; + u8c->ss = u8c->s; + u8c->slen = u8c->len; + if (!u8c->p) + u8c->len -= utf8clen(u8c->s); + u8c->s += utf8clen(u8c->s); + } else if (ccc != STOPPER) { + /* Not a stopper, and not the ccc we're emitting. */ + if (!u8c->p) + u8c->len -= utf8clen(u8c->s); + u8c->s += utf8clen(u8c->s); + } else if (u8c->nccc != MAXCCC + 1) { + /* At a stopper, restart for next ccc. */ + u8c->ccc = u8c->nccc; + u8c->nccc = MAXCCC + 1; + u8c->s = u8c->ss; + u8c->p = u8c->sp; + u8c->len = u8c->slen; + } else { + /* All done, proceed from here. */ + u8c->ccc = STOPPER; + u8c->nccc = STOPPER; + u8c->sp = NULL; + u8c->ss = NULL; + u8c->slen = 0; + } + } +} + +/* ------------------------------------------------------------------ */ + +static int normalize_line(struct tree *tree) +{ + char *s; + char *t; + int c; + struct utf8cursor u8c; + + /* First test: null-terminated string. */ + s = buf2; + t = buf3; + if (utf8cursor(&u8c, tree, s)) + return -1; + while ((c = utf8byte(&u8c)) > 0) + if (c != (unsigned char)*t++) + return -1; + if (c < 0) + return -1; + if (*t != 0) + return -1; + + /* Second test: length-limited string. */ + s = buf2; + /* Replace NUL with a value that will cause an error if seen. */ + s[strlen(s) + 1] = -1; + t = buf3; + if (utf8cursor(&u8c, tree, s)) + return -1; + while ((c = utf8byte(&u8c)) > 0) + if (c != (unsigned char)*t++) + return -1; + if (c < 0) + return -1; + if (*t != 0) + return -1; + + return 0; +} + +static void normalization_test(void) +{ + FILE *file; + unsigned int unichar; + struct unicode_data *data; + char *s; + char *t; + int ret; + int ignorables; + int tests = 0; + int failures = 0; + + if (verbose > 0) + printf("Parsing %s\n", test_name); + /* Step one, read data from file. */ + file = fopen(test_name, "r"); + if (!file) + open_fail(test_name, errno); + + while (fgets(line, LINESIZE, file)) { + ret = sscanf(line, "%[^;];%*[^;];%*[^;];%*[^;];%[^;];", + buf0, buf1); + if (ret != 2 || *line == '#') + continue; + s = buf0; + t = buf2; + while (*s) { + unichar = strtoul(s, &s, 16); + t += utf8encode(t, unichar); + } + *t = '\0'; + + ignorables = 0; + s = buf1; + t = buf3; + while (*s) { + unichar = strtoul(s, &s, 16); + data = &unicode_data[unichar]; + if (data->utf8nfkdi && !*data->utf8nfkdi) + ignorables = 1; + else + t += utf8encode(t, unichar); + } + *t = '\0'; + + tests++; + if (normalize_line(nfkdi_tree) < 0) { + printf("Line %s -> %s", buf0, buf1); + if (ignorables) + printf(" (ignorables removed)"); + printf(" failure\n"); + failures++; + } + } + fclose(file); + if (verbose > 0) + printf("Ran %d tests with %d failures\n", tests, failures); + if (failures) + file_fail(test_name); +} + +/* ------------------------------------------------------------------ */ + +static void write_file(void) +{ + FILE *file; + int i; + int j; + int t; + int gen; + + if (verbose > 0) + printf("Writing %s\n", utf8_name); + file = fopen(utf8_name, "w"); + if (!file) + open_fail(utf8_name, errno); + + fprintf(file, "/* This file is generated code, do not edit. */\n"); + fprintf(file, "#ifndef __INCLUDED_FROM_UTF8NORM_C__\n"); + fprintf(file, "#error Only nls_utf8-norm.c should include this file.\n"); + fprintf(file, "#endif\n"); + fprintf(file, "\n"); + fprintf(file, "static const unsigned int utf8vers = %#x;\n", + unicode_maxage); + fprintf(file, "\n"); + fprintf(file, "static const unsigned int utf8agetab[] = {\n"); + for (i = 0; i != ages_count; i++) + fprintf(file, "\t%#x%s\n", ages[i], + ages[i] == unicode_maxage ? "" : ","); + fprintf(file, "};\n"); + fprintf(file, "\n"); + fprintf(file, "static const struct utf8data utf8nfkdicfdata[] = {\n"); + t = 0; + for (gen = 0; gen < ages_count; gen++) { + fprintf(file, "\t{ %#x, %d }%s\n", + ages[gen], trees[t].index, + ages[gen] == unicode_maxage ? "" : ","); + if (trees[t].maxage == ages[gen]) + t += 2; + } + fprintf(file, "};\n"); + fprintf(file, "\n"); + fprintf(file, "static const struct utf8data utf8nfkdidata[] = {\n"); + t = 1; + for (gen = 0; gen < ages_count; gen++) { + fprintf(file, "\t{ %#x, %d }%s\n", + ages[gen], trees[t].index, + ages[gen] == unicode_maxage ? "" : ","); + if (trees[t].maxage == ages[gen]) + t += 2; + } + fprintf(file, "};\n"); + fprintf(file, "\n"); + fprintf(file, "static const unsigned char utf8data[%zd] = {\n", + utf8data_size); + t = 0; + for (i = 0; i != utf8data_size; i += 16) { + if (i == trees[t].index) { + fprintf(file, "\t/* %s_%x */\n", + trees[t].type, trees[t].maxage); + if (t < trees_count-1) + t++; + } + fprintf(file, "\t"); + for (j = i; j != i + 16; j++) + fprintf(file, "0x%.2x%s", utf8data[j], + (j < utf8data_size -1 ? "," : "")); + fprintf(file, "\n"); + } + fprintf(file, "};\n"); + fclose(file); +} + +/* ------------------------------------------------------------------ */ + +int main(int argc, char *argv[]) +{ + unsigned int unichar; + int opt; + + argv0 = argv[0]; + + while ((opt = getopt(argc, argv, "a:c:d:f:hn:o:p:t:v")) != -1) { + switch (opt) { + case 'a': + age_name = optarg; + break; + case 'c': + ccc_name = optarg; + break; + case 'd': + data_name = optarg; + break; + case 'f': + fold_name = optarg; + break; + case 'n': + norm_name = optarg; + break; + case 'o': + utf8_name = optarg; + break; + case 'p': + prop_name = optarg; + break; + case 't': + test_name = optarg; + break; + case 'v': + verbose++; + break; + case 'h': + help(); + exit(0); + default: + usage(); + } + } + + if (verbose > 1) + help(); + for (unichar = 0; unichar != 0x110000; unichar++) + unicode_data[unichar].code = unichar; + age_init(); + ccc_init(); + nfkdi_init(); + nfkdicf_init(); + ignore_init(); + corrections_init(); + hangul_decompose(); + nfkdi_decompose(); + nfkdicf_decompose(); + utf8_init(); + trees_init(); + trees_populate(); + trees_reduce(); + trees_verify(); + /* Prevent "unused function" warning. */ + (void)lookup(nfkdi_tree, " "); + if (verbose > 2) + tree_walk(nfkdi_tree); + if (verbose > 2) + tree_walk(nfkdicf_tree); + normalization_test(); + write_file(); + + return 0; +} diff --git a/util/subst.c b/util/subst.c new file mode 100644 index 0000000..be2a0dd --- /dev/null +++ b/util/subst.c @@ -0,0 +1,468 @@ +/* + * subst.c --- substitution program + * + * Subst is used as a quickie program to do @ substitutions + * + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#else +#define HAVE_SYS_STAT_H +#define HAVE_SYS_TIME_H +#endif +#include +#include +#include +#include +#include +#include +#ifdef HAVE_SYS_TIME_H +#include +#endif +#ifdef HAVE_SYS_TYPES_H +#include +#endif +#ifdef HAVE_SYS_STAT_H +#include +#endif +#include +#include +#include +#ifdef HAVE_SYS_TIME_H +#include +#endif + +#ifdef HAVE_GETOPT_H +#include +#else +extern char *optarg; +extern int optind; +#endif + + +struct subst_entry { + char *name; + char *value; + struct subst_entry *next; +}; + +static struct subst_entry *subst_table = 0; + +static int add_subst(char *name, char *value) +{ + struct subst_entry *ent = 0; + + ent = (struct subst_entry *) malloc(sizeof(struct subst_entry)); + if (!ent) + goto fail; + ent->name = (char *) malloc(strlen(name)+1); + if (!ent->name) + goto fail; + ent->value = (char *) malloc(strlen(value)+1); + if (!ent->value) + goto fail; + strcpy(ent->name, name); + strcpy(ent->value, value); + ent->next = subst_table; + subst_table = ent; + return 0; +fail: + if (ent) { + free(ent->name); + free(ent); + } + return ENOMEM; +} + +static struct subst_entry *fetch_subst_entry(char *name) +{ + struct subst_entry *ent; + + for (ent = subst_table; ent; ent = ent->next) { + if (strcmp(name, ent->name) == 0) + break; + } + return ent; +} + +/* + * Given the starting and ending position of the replacement name, + * check to see if it is valid, and pull it out if it is. + */ +static char *get_subst_symbol(const char *begin, size_t len, char prefix) +{ + static char replace_name[128]; + char *cp, *start; + + start = replace_name; + if (prefix) + *start++ = prefix; + + if (len > sizeof(replace_name)-2) + return NULL; + memcpy(start, begin, len); + start[len] = 0; + + /* + * The substitution variable must all be in the of [0-9A-Za-z_]. + * If it isn't, this must be an invalid symbol name. + */ + for (cp = start; *cp; cp++) { + if (!(*cp >= 'a' && *cp <= 'z') && + !(*cp >= 'A' && *cp <= 'Z') && + !(*cp >= '0' && *cp <= '9') && + !(*cp == '_')) + return NULL; + } + return (replace_name); +} + +static void replace_string(char *begin, char *end, char *newstr) +{ + int replace_len, len; + + replace_len = strlen(newstr); + len = end - begin; + if (replace_len == 0) + memmove(begin, end+1, strlen(end)+1); + else if (replace_len != len+1) + memmove(end+(replace_len-len-1), end, + strlen(end)+1); + memcpy(begin, newstr, replace_len); +} + +static void substitute_line(char *line) +{ + char *ptr, *name_ptr, *end_ptr; + struct subst_entry *ent; + char *replace_name; + size_t len; + + /* + * Expand all @FOO@ substitutions + */ + ptr = line; + while (ptr) { + name_ptr = strchr(ptr, '@'); + if (!name_ptr) + break; /* No more */ + if (*(++name_ptr) == '@') { + /* + * Handle tytso@@mit.edu --> tytso@mit.edu + */ + memmove(name_ptr-1, name_ptr, strlen(name_ptr)+1); + ptr = name_ptr+1; + continue; + } + end_ptr = strchr(name_ptr, '@'); + if (!end_ptr) + break; + len = end_ptr - name_ptr; + replace_name = get_subst_symbol(name_ptr, len, 0); + if (!replace_name) { + ptr = name_ptr; + continue; + } + ent = fetch_subst_entry(replace_name); + if (!ent) { + fprintf(stderr, "Unfound expansion: '%s'\n", + replace_name); + ptr = end_ptr + 1; + continue; + } +#if 0 + fprintf(stderr, "Replace name = '%s' with '%s'\n", + replace_name, ent->value); +#endif + ptr = name_ptr-1; + replace_string(ptr, end_ptr, ent->value); + if ((ent->value[0] == '@') && + (strlen(replace_name) == strlen(ent->value)-2) && + !strncmp(replace_name, ent->value+1, + strlen(ent->value)-2)) + /* avoid an infinite loop */ + ptr += strlen(ent->value); + } + /* + * Now do a second pass to expand ${FOO} + */ + ptr = line; + while (ptr) { + name_ptr = strchr(ptr, '$'); + if (!name_ptr) + break; /* No more */ + if (*(++name_ptr) != '{') { + ptr = name_ptr; + continue; + } + name_ptr++; + end_ptr = strchr(name_ptr, '}'); + if (!end_ptr) + break; + len = end_ptr - name_ptr; + replace_name = get_subst_symbol(name_ptr, len, '$'); + if (!replace_name) { + ptr = name_ptr; + continue; + } + ent = fetch_subst_entry(replace_name); + if (!ent) { + ptr = end_ptr + 1; + continue; + } +#if 0 + fprintf(stderr, "Replace name = '%s' with '%s'\n", + replace_name, ent->value); +#endif + ptr = name_ptr-2; + replace_string(ptr, end_ptr, ent->value); + } +} + +static void parse_config_file(FILE *f) +{ + char line[2048]; + char *cp, *ptr; + + while (!feof(f)) { + memset(line, 0, sizeof(line)); + if (fgets(line, sizeof(line), f) == NULL) + break; + /* + * Strip newlines and comments. + */ + cp = strchr(line, '\n'); + if (cp) + *cp = 0; + cp = strchr(line, '#'); + if (cp) + *cp = 0; + /* + * Skip trailing and leading whitespace + */ + for (cp = line + strlen(line) - 1; cp >= line; cp--) { + if (*cp == ' ' || *cp == '\t') + *cp = 0; + else + break; + } + cp = line; + while (*cp && isspace(*cp)) + cp++; + ptr = cp; + /* + * Skip empty lines + */ + if (*ptr == 0) + continue; + /* + * Ignore future extensions + */ + if (*ptr == '@') + continue; + /* + * Parse substitutions + */ + for (cp = ptr; *cp; cp++) + if (isspace(*cp)) + break; + *cp = 0; + for (cp++; *cp; cp++) + if (!isspace(*cp)) + break; +#if 0 + printf("Substitute: '%s' for '%s'\n", ptr, cp ? cp : ""); +#endif + add_subst(ptr, cp); + } +} + +/* + * Return 0 if the files are different, 1 if the files are the same. + */ +static int compare_file(FILE *old_f, FILE *new_f) +{ + char oldbuf[2048], newbuf[2048], *oldcp, *newcp; + int retval; + + while (1) { + oldcp = fgets(oldbuf, sizeof(oldbuf), old_f); + newcp = fgets(newbuf, sizeof(newbuf), new_f); + if (!oldcp && !newcp) { + retval = 1; + break; + } + if (!oldcp || !newcp || strcmp(oldbuf, newbuf)) { + retval = 0; + break; + } + } + return retval; +} + +void set_utimes(const char *filename, int fd, const struct timeval times[2]) +{ +#ifdef HAVE_FUTIMES + if (futimes(fd, times) < 0) + perror("futimes"); +#elif HAVE_UTIMES + if (utimes(filename, times) < 0) + perror("utimes"); +#else + struct utimbuf ut; + + ut.actime = times[0].tv_sec; + ut.modtime = times[1].tv_sec; + if (utime(filename, &ut) < 0) + perror("utime"); +#endif +} + + +int main(int argc, char **argv) +{ + char line[2048]; + int c; + int fd, ofd = -1; + FILE *in, *out, *old = NULL; + char *outfn = NULL, *newfn = NULL; + int verbose = 0; + int adjust_timestamp = 0; + int got_atime = 0; + struct stat stbuf; + struct timeval tv[2]; + + while ((c = getopt (argc, argv, "f:tv")) != EOF) { + switch (c) { + case 'f': + in = fopen(optarg, "r"); + if (!in) { + perror(optarg); + exit(1); + } + parse_config_file(in); + fclose(in); + break; + case 't': + adjust_timestamp++; + break; + case 'v': + verbose++; + break; + default: + fprintf(stderr, "%s: [-f config-file] [file]\n", + argv[0]); + break; + } + } + if (optind < argc) { + in = fopen(argv[optind], "r"); + if (!in) { + perror(argv[optind]); + exit(1); + } + optind++; + } else + in = stdin; + + if (optind < argc) { + outfn = argv[optind]; + newfn = (char *) malloc(strlen(outfn)+20); + if (!newfn) { + fprintf(stderr, "Memory error! Exiting.\n"); + exit(1); + } + strcpy(newfn, outfn); + strcat(newfn, ".new"); + ofd = open(newfn, O_CREAT|O_TRUNC|O_RDWR, 0644); + if (ofd < 0) { + perror(newfn); + exit(1); + } + out = fdopen(ofd, "w+"); + if (!out) { + perror("fdopen"); + exit(1); + } + + fd = open(outfn, O_RDONLY); + if (fd > 0) { + /* save the original atime, if possible */ + if (fstat(fd, &stbuf) == 0) { +#if HAVE_STRUCT_STAT_ST_ATIM + tv[0].tv_sec = stbuf.st_atim.tv_sec; + tv[0].tv_usec = stbuf.st_atim.tv_nsec / 1000; +#else + tv[0].tv_sec = stbuf.st_atime; + tv[0].tv_usec = 0; +#endif + got_atime = 1; + } + old = fdopen(fd, "r"); + if (!old) + close(fd); + } + } else { + out = stdout; + outfn = 0; + } + + while (!feof(in)) { + if (fgets(line, sizeof(line), in) == NULL) + break; + substitute_line(line); + fputs(line, out); + } + fclose(in); + if (outfn) { + fflush(out); + rewind(out); + if (old && compare_file(old, out)) { + if (verbose) + printf("No change, keeping %s.\n", outfn); + if (adjust_timestamp) { + if (verbose) + printf("Updating modtime for %s\n", outfn); + if (gettimeofday(&tv[1], NULL) < 0) { + perror("gettimeofday"); + exit(1); + } + if (got_atime == 0) + tv[0] = tv[1]; + else if (verbose) + printf("Using original atime\n"); + set_utimes(outfn, fileno(old), tv); + } +#ifndef _WIN32 + if (ofd >= 0) + (void) fchmod(ofd, 0444); +#endif + fclose(out); + if (unlink(newfn) < 0) + perror("unlink"); + } else { + if (verbose) + printf("Creating or replacing %s.\n", outfn); +#ifndef _WIN32 + if (ofd >= 0) + (void) fchmod(ofd, 0444); +#endif + fclose(out); + if (old) + fclose(old); + old = NULL; + if (rename(newfn, outfn) < 0) { + perror("rename"); + exit(1); + } + } + } + if (old) + fclose(old); + if (newfn) + free(newfn); + return (0); +} + + diff --git a/util/subst.conf.in b/util/subst.conf.in new file mode 100644 index 0000000..0da4554 --- /dev/null +++ b/util/subst.conf.in @@ -0,0 +1,26 @@ +AWK @AWK@ +SED @SED@ +E2FSPROGS_MONTH @E2FSPROGS_MONTH@ +E2FSPROGS_YEAR @E2FSPROGS_YEAR@ +E2FSPROGS_DATE @E2FSPROGS_DATE@ +E2FSPROGS_VERSION @E2FSPROGS_VERSION@ +SIZEOF_LONG_LONG @SIZEOF_LONG_LONG@ +SIZEOF_LONG @SIZEOF_LONG@ +SIZEOF_INT @SIZEOF_INT@ +SIZEOF_SHORT @SIZEOF_SHORT@ +datarootdir @datarootdir@ +datadir @datadir@ +root_sysconfdir @root_sysconfdir@ +$datarootdir @datarootdir@ +$root_prefix @root_prefix@ +$prefix @prefix@ +# Enable the documentation for the journal device mke2fs, tune2fs, and +# e2fsck's man page +JDEV +# Enable the documentation for the tdb profile in e2fsck.conf's man page +TDB_MAN_COMMENT @TDB_MAN_COMMENT@ +root_sbindir @root_sbindir@ +root_bindir @root_bindir@ +libdir @libdir@ +$exec_prefix @exec_prefix@ +pkglibdir @libdir@/e2fsprogs diff --git a/util/symlinks.c b/util/symlinks.c new file mode 100644 index 0000000..e9d2b01 --- /dev/null +++ b/util/symlinks.c @@ -0,0 +1,391 @@ +#define _FILE_OFFSET_BITS 64 +#ifndef _LARGEFILE_SOURCE +#define _LARGEFILE_SOURCE +#endif +#ifndef _LARGEFILE64_SOURCE +#define _LARGEFILE64_SOURCE +#endif + +#include +#ifndef _POSIX_SOURCE +#define _POSIX_SOURCE +#endif +#include +#include +#ifdef HAVE_MALLOC_H +#include +#endif +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#ifndef S_ISLNK +#define S_ISLNK(mode) (((mode) & (_S_IFMT)) == (_S_IFLNK)) +#endif + +#ifndef PATH_MAX +#define PATH_MAX 1024 +#endif + +#define progver "%s: scan/change symbolic links - v1.3 - by Mark Lord\n\n" +static char *progname; +static int verbose = 0, fix_links = 0, recurse = 0, delete = 0, shorten = 0, + testing = 0, single_fs = 1; + +/* + * tidypath removes excess slashes and "." references from a path string + */ + +static int substr (char *s, char *old, char *new) +{ + char *tmp = NULL; + int oldlen = strlen(old), newlen = 0; + + if (NULL == strstr(s, old)) + return 0; + + if (new) + newlen = strlen(new); + + if (newlen > oldlen) { + if ((tmp = malloc(strlen(s))) == NULL) { + fprintf(stderr, "no memory\n"); + exit (1); + } + } + + while (NULL != (s = strstr(s, old))) { + char *p, *old_s = s; + + if (new) { + if (newlen > oldlen) + old_s = strcpy(tmp, s); + p = new; + while (*p) + *s++ = *p++; + } + p = old_s + oldlen; + while ((*s++ = *p++)); + } + if (tmp) + free(tmp); + return 1; +} + + +static int tidy_path (char *path) +{ + int tidied = 0; + char *s, *p; + + s = path + strlen(path) - 1; + if (s[0] != '/') { /* tmp trailing slash simplifies things */ + s[1] = '/'; + s[2] = '\0'; + } + while (substr(path, "/./", "/")) + tidied = 1; + while (substr(path, "//", "/")) + tidied = 1; + + while ((p = strstr(path,"/../")) != NULL) { + s = p+3; + for (p--; p != path; p--) if (*p == '/') break; + if (*p != '/') + break; + while ((*p++ = *s++)); + tidied = 1; + } + if (*path == '\0') + strcpy(path,"/"); + p = path + strlen(path) - 1; + if (p != path && *p == '/') + *p-- = '\0'; /* remove tmp trailing slash */ + while (p != path && *p == '/') { /* remove any others */ + *p-- = '\0'; + tidied = 1; + } + while (!strncmp(path,"./",2)) { + for (p = path, s = path+2; (*p++ = *s++);); + tidied = 1; + } + return tidied; +} + +static int shorten_path (char *path, char *abspath) +{ + static char dir[PATH_MAX]; + int shortened = 0; + char *p; + + /* get rid of unnecessary "../dir" sequences */ + while (abspath && strlen(abspath) > 1 && (p = strstr(path,"../"))) { + /* find innermost occurrence of "../dir", and save "dir" */ + int slashes = 2; + char *a, *s, *d = dir; + while ((s = strstr(p+3, "../"))) { + ++slashes; + p = s; + } + s = p+3; + *d++ = '/'; + while (*s && *s != '/') + *d++ = *s++; + *d++ = '/'; + *d = '\0'; + if (!strcmp(dir,"//")) + break; + /* note: p still points at ../dir */ + if (*s != '/' || !*++s) + break; + a = abspath + strlen(abspath) - 1; + while (slashes-- > 0) { + if (a <= abspath) + goto ughh; + while (*--a != '/') { + if (a <= abspath) + goto ughh; + } + } + if (strncmp(dir, a, strlen(dir))) + break; + while ((*p++ = *s++)); /* delete the ../dir */ + shortened = 1; + } +ughh: + return shortened; +} + + +static void fix_symlink (char *path, dev_t my_dev) +{ + static char lpath[PATH_MAX], new[PATH_MAX], abspath[PATH_MAX]; + char *p, *np, *lp, *tail, *msg; + struct stat stbuf, lstbuf; + int c, fix_abs = 0, fix_messy = 0, fix_long = 0; + + if ((c = readlink(path, lpath, sizeof(lpath) - 1)) == -1) { + perror(path); + return; + } + lpath[c] = '\0'; /* readlink does not null terminate it */ + + /* construct the absolute address of the link */ + abspath[0] = '\0'; + if (lpath[0] != '/') { + strcat(abspath,path); + c = strlen(abspath); + if ((c > 0) && (abspath[c-1] == '/')) + abspath[c-1] = '\0'; /* cut trailing / */ + if ((p = strrchr(abspath,'/')) != NULL) + *p = '\0'; /* cut last component */ + strcat(abspath,"/"); + } + strcat(abspath,lpath); + (void) tidy_path(abspath); + + /* check for various things */ + if (stat(abspath, &stbuf) == -1) { + printf("dangling: %s -> %s\n", path, lpath); + if (delete) { + if (unlink (path)) { + perror(path); + } else + printf("deleted: %s -> %s\n", path, lpath); + } + return; + } + + if (single_fs) + lstat(abspath, &lstbuf); /* if the above didn't fail, then this shouldn't */ + + if (single_fs && lstbuf.st_dev != my_dev) { + msg = "other_fs:"; + } else if (lpath[0] == '/') { + msg = "absolute:"; + fix_abs = 1; + } else if (verbose) { + msg = "relative:"; + } else + msg = NULL; + fix_messy = tidy_path(strcpy(new,lpath)); + if (shorten) + fix_long = shorten_path(new, path); + if (!fix_abs) { + if (fix_messy) + msg = "messy: "; + else if (fix_long) + msg = "lengthy: "; + } + if (msg != NULL) + printf("%s %s -> %s\n", msg, path, lpath); + if (!(fix_links || testing) || !(fix_messy || fix_abs || fix_long)) + return; + + if (fix_abs) { + /* convert an absolute link to relative: */ + /* point tail at first part of lpath that differs from path */ + /* point p at first part of path that differs from lpath */ + (void) tidy_path(lpath); + tail = lp = lpath; + p = path; + while (*p && (*p == *lp)) { + if (*lp++ == '/') { + tail = lp; + while (*++p == '/'); + } + } + + /* now create new, with "../"s followed by tail */ + np = new; + while (*p) { + if (*p++ == '/') { + *np++ = '.'; + *np++ = '.'; + *np++ = '/'; + while (*p == '/') ++p; + } + } + strcpy (np, tail); + (void) tidy_path(new); + if (shorten) (void) shorten_path(new, path); + } + shorten_path(new,path); + if (!testing) { + if (unlink (path)) { + perror(path); + return; + } + if (symlink(new, path)) { + perror(path); + return; + } + } + printf("changed: %s -> %s\n", path, new); +} + +static void dirwalk (char *path, int pathlen, dev_t dev) +{ + char *name; + DIR *dfd; + static struct stat st; + static struct dirent *dp; + + if ((dfd = opendir(path)) == NULL) { + perror(path); + return; + } + + name = path + pathlen; + if (*(name-1) != '/') + *name++ = '/'; + + while ((dp = readdir(dfd)) != NULL ) { + strcpy(name, dp->d_name); + if (strcmp(name, ".") && strcmp(name,"..")) { + if (lstat(path, &st) == -1) { + perror(path); + } else if (st.st_dev == dev) { + if (S_ISLNK(st.st_mode)) { + fix_symlink (path, dev); + } else if (recurse && S_ISDIR(st.st_mode)) { + dirwalk(path, strlen(path), dev); + } + } + } + } + closedir(dfd); + path[pathlen] = '\0'; +} + +static void usage_error (void) +{ + fprintf(stderr, progver, progname); + fprintf(stderr, "Usage:\t%s [-cdorstv] LINK|DIR ...\n\n", progname); + fprintf(stderr, "Flags:" + "\t-c == change absolute/messy links to relative\n" + "\t-d == delete dangling links\n" + "\t-o == warn about links across file systems\n" + "\t-r == recurse into subdirs\n" + "\t-s == shorten lengthy links (displayed in output only when -c not specified)\n" + "\t-t == show what would be done by -c\n" + "\t-v == verbose (show all symlinks)\n\n"); + exit(1); +} + +int main(int argc, char **argv) +{ +#if defined (_GNU_SOURCE) && defined (__GLIBC__) + static char path[PATH_MAX+2]; + char* cwd = get_current_dir_name(); +#else + static char path[PATH_MAX+2], cwd[PATH_MAX+2]; +#endif + int dircount = 0; + char c, *p; + + if ((progname = (char *) strrchr(*argv, '/')) == NULL) + progname = *argv; + else + progname++; + +#if defined (_GNU_SOURCE) && defined (__GLIBC__) + if (NULL == cwd) { + fprintf(stderr,"get_current_dir_name() failed\n"); +#else + if (NULL == getcwd(cwd,PATH_MAX)) { + fprintf(stderr,"getcwd() failed\n"); +#endif + exit (1); + } +#if defined (_GNU_SOURCE) && defined (__GLIBC__) + cwd = realloc(cwd, strlen(cwd)+2); + if (cwd == NULL) { + fprintf(stderr, "realloc() failed\n"); + exit (1); + } +#endif + if (!*cwd || cwd[strlen(cwd)-1] != '/') + strcat(cwd,"/"); + + while (--argc) { + p = *++argv; + if (*p == '-') { + if (*++p == '\0') + usage_error(); + while ((c = *p++)) { + if (c == 'c') fix_links = 1; + else if (c == 'd') delete = 1; + else if (c == 'o') single_fs = 0; + else if (c == 'r') recurse = 1; + else if (c == 's') shorten = 1; + else if (c == 't') testing = 1; + else if (c == 'v') verbose = 1; + else usage_error(); + } + } else { + struct stat st; + if (*p == '/') + *path = '\0'; + else + strcpy(path,cwd); + tidy_path(strcat(path, p)); + if (lstat(path, &st) == -1) + perror(path); + else if (S_ISLNK(st.st_mode)) + fix_symlink(path, st.st_dev); + else + dirwalk(path, strlen(path), st.st_dev); + ++dircount; + } + } + if (dircount == 0) + usage_error(); + exit (0); +} diff --git a/util/ucd/README b/util/ucd/README new file mode 100644 index 0000000..9fed514 --- /dev/null +++ b/util/ucd/README @@ -0,0 +1,37 @@ +The files in this directory are part of the Unicode Character Database +for version 11.0.0 of the Unicode standard. + +The full set of UCD files are not distributed with e2fsprogs, since they +are very large and only needed to regenerate the lib/ext2fs/utf8data.h +during an Unicode version update. They can be found in the link below +and also in the Linux kernel source tree: + + http://www.unicode.org/Public/11.0.0/ucd/ + +The latest released version of the UCD can be found here: + + http://www.unicode.org/Public/UCD/latest/ + +The files in this directory are identical, except that they have been +renamed with a suffix indicating the unicode version. + +Individual source links: + + http://www.unicode.org/Public/11.0.0/ucd/CaseFolding.txt + http://www.unicode.org/Public/11.0.0/ucd/DerivedAge.txt + http://www.unicode.org/Public/11.0.0/ucd/extracted/DerivedCombiningClass.txt + http://www.unicode.org/Public/11.0.0/ucd/DerivedCoreProperties.txt + http://www.unicode.org/Public/11.0.0/ucd/NormalizationCorrections.txt + http://www.unicode.org/Public/11.0.0/ucd/NormalizationTest.txt + http://www.unicode.org/Public/11.0.0/ucd/UnicodeData.txt + +md5sums + + 414436796cf097df55f798e1585448ee CaseFolding-11.0.0.txt + 6032a595fbb782694456491d86eecfac DerivedAge-11.0.0.txt + 3240997d671297ac754ab0d27577acf7 DerivedCombiningClass-11.0.0.txt + d41d8cd98f00b204e9800998ecf8427e DerivedCombiningClass.txt + 2a4fe257d9d8184518e036194d2248ec DerivedCoreProperties-11.0.0.txt + 4e7d383fa0dd3cd9d49d64e5b7b7c9e0 NormalizationCorrections-11.0.0.txt + c9500c5b8b88e584469f056023ecc3f2 NormalizationTest-11.0.0.txt + acc291106c3758d2025f8d7bd5518bee UnicodeData-11.0.0.txt -- cgit v1.2.3