src-test/usr.bin/sort, branch main

Fix -Wpointer-sign warnings in bwstring.c

2020-09-10T15:37:19Z

sort(1): Remove duplicate option check

2020-09-08T15:01:49Z

Reviewed by: lwhsu, emaste Approved by: emaste Obtained from: DragonFlyBSD MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D23892

sort(1): Fix two wchar-related bugs in radixsort

2020-06-23T16:43:48Z

Sort(1)'s radixsort implementation was broken for multibyte LC_CTYPEs in at least two ways: * In actual radix sort, it would only bucket the least significant byte from each wchar, ignoring the 24 most-significant bits of each unicode character. * In degenerate cases / "fast paths," it would fall back to another sorting algorithm (default: mergesort) with a bogus comparator offset. The string comparison functions in sort(1) take an offset in units of the operating character size. However, radixsort was passing an offset in units of bytes. The byte offset must be divided by sizeof(wchar_t). This revision addresses both discovered issues. Some example testcases: $ (echo 耳 ; echo 脳 ; echo 耳) | \ LC_CTYPE=ja_JP.UTF-8 LC_COLLATE=C LANG=C sort --radixsort --debug $ (echo 耳 ; echo 脳 ; echo 耳) | \ LC_CTYPE=C LC_COLLATE=C LANG=C sort --radixsort --debug $ (for i in $(jot 34); do echo 耳耳耳耳耳; echo 耳耳耳耳脳; echo 耳耳耳耳脴; done) | \ LC_CTYPE=ja_JP.UTF-8 LC_COLLATE=C LANG=C sort --radixsort --debug PR: 247494 Reported by: knu MFC after: I do not intend to, but parties interested in stable might want to

Update Makefile.depend files

2019-12-11T17:37:53Z

Update a bunch of Makefile.depend files as a result of adding Makefile.depend.options files Reviewed by: bdrewery MFC after: 1 week Sponsored by: Juniper Networks Differential Revision: https://reviews.freebsd.org/D22494

Add Makefile.depend.options

2019-12-11T17:37:37Z

Leaf directories that have dependencies impacted by options need a Makefile.depend.options file to avoid churn in Makefile.depend DIRDEPS for cases such as OPENSSL, TCP_WRAPPERS etc can be set in local.dirdeps-options.mk which can add to those set in Makefile.depend.options See share/mk/dirdeps-options.mk Reviewed by: bdrewery MFC after: 1 week Sponsored by: Juniper Networks Differential Revision: https://reviews.freebsd.org/D22469

Adjust history, info source from v1's manuals

2019-09-04T13:44:46Z

https://www.bell-labs.com/usr/dmr/www/1stEdman.html MFC after: 5 days

sort(1): Memoize MD5 computation to reduce repeated computation

2019-04-13T04:42:17Z

Experimentally, reduces sort -R time of a 148160 line corpus from about 3.15s to about 0.93s on this particular system. There's probably room for improvement using some digest other than md5, but I don't want to look at sort(1) anymore. Some discussion of other possible improvements in the Test Plan section of the Differential. PR: 230792 Reviewed by: jhb (earlier version) Differential Revision: https://reviews.freebsd.org/D19885

sort(1): Simplify and bound random seeding

2019-04-11T05:08:49Z

Bound input file processing length to avoid the issue reported in [1]. For simplicity, only allow regular file and character device inputs. For character devices, only allow /dev/random (and /dev/urandom symblink). 32 bytes of random is perfectly sufficient to seed MD5; we don't need any more. Users that want to use large files as seeds are encouraged to truncate those files down to an appropriate input file via tools like sha256(1). (This does not change the sort algorithm of sort -R.) [1]: https://lists.freebsd.org/pipermail/freebsd-hackers/2018-August/053152.html PR: 230792 Reported by: Ali Abdallah Relnotes: yes

sort(1): Whitespace and style cleanup

2019-04-11T00:39:06Z

No functional change. Sponsored by: Dell EMC Isilon

sort(1): randomcoll: Skip the memory allocation entirely

2019-04-04T23:32:27Z

There's no reason to order based on strcmp of ASCII digests instead of memcmp of the raw digests. While here, remove collision fallback. If you collide two MD5s, they're probably the same string anyway. If robustness against MD5 collisions is desired, maybe we shouldn't use MD5. None of the behavior of sort -R is specified by POSIX, so we're free to implement this however we like. E.g., using a 128-bit counter and block cipher to generate unique indices for each line of input. PR: 230792 (2/many) Relnotes: This will change the sort order for a given dataset with a given seed. Other similarly breaking changes are planned. Sponsored by: Dell EMC Isilon