suffix array construction with SA-IS in x86 assembly
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
CHANGES
COPYING
Makefile
README
sais-chr.S
sais-chr.orig.c
sais.S
sais.h
sais.orig.c
suftest.c

README

sais-x86
========

Sais-x86 is an implementation of the IS (induced sorting) suffix array
construction algorithm in x86-64 assembly for systems following the
SysV ABI.

This implementation seems to be about 15% faster than sais-lite due to
various small optimisations.  I expect further performance improvements
to occur by vectorising the code, but I have not gotten around doing
that so far.

Sais-x86 is based on sais-lite 2.4.1 by Yuta Mori <yuta.256@gmail.com>

The SA-IS algorithm was first described in:

Ge Nong, Sen Zhang, and Wai Hong Chang: "Two Efficient Algorithms for
Linear Suffix Array Construction", IEEE Transactions on Computers,
vol. 60(10), p. 1471--1484, Oct. 2011.