Internet-Draft submission

idnits 2.15.01 

/a/www/www6s/staging/draft-ray-radx-01.txt:

  Showing Errors (**), Flaws (~~), Warnings (==), and Comments (--).
  Errors MUST be fixed before draft submission.  Flaws SHOULD be fixed before draft submission.

  Checking boilerplate required by RFC 5378 and the IETF Trust (see
  https://trustee.ietf.org/license-info):
  ----------------------------------------------------------------------------

     No issues found here.

  Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
  ----------------------------------------------------------------------------

     No issues found here.

  Running in submission checking mode -- *not* checking nits according to
  https://www.ietf.org/id-info/checklist .
  ----------------------------------------------------------------------------


     No nits found.

INTERNET-DRAFT                                           D. Ray de Silva
Intended status: Standard                                   Ray de Silva
File: draft-ray-radx-01                                 17 February 2018
Expires: 1 September 2018

             Low Overhead Compression For Short String Data

Copyright (c) 2018 IETF Trust and the persons identified as the document
authors.  All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions
Relating to IETF Documents (https://trustee.ietf.org/license-info) in
effect on the date of publication of this document.  Please review these
documents carefully, as they describe your rights and restrictions with
respect to this document.

This Internet-Draft is submitted in full conformance with the provisions
of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet  Engineering  Task
Force (IETF), its areas, and its working groups.  Note that other groups
may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time.  It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html

The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

ABSTRACT

Compression methods primarily rely on detecting patterns of redundancy
in text strings, which means that a minimum of around 800 bytes of data
are required before compression can occur.  Most data fields in data-
bases are far smaller than that, and therefore dictionary-based compres-
sion is not efficient.  The method proposed begins by making assumptions
about the data and accepting some compromises; which allows compression
to begin from the very first byte.  The discussion proves that this can
result in 1) an average 30% compression, 2) a maximum 50% compression,
and 3) no expansion at all (0%) of the input data.  As an added benefit,
all processing can be performed using bit shifting and masking, which
drastically lowers the cost of compression; no division or multiplica-
tion operations are necessary.  UTF-8 text is handled gracefully.

OVERVIEW AND BACKGROUND

The origin of RadX is the attempt by Digital Equipment Corporation in
the 1970's to pack more text into the limited memory space available to
computers in that era, particularly as DEC was supporting different
classes of machines with different word sizes - some, like the PDP/8
series, were byte machines, but some used 32 or even 36 bits.
DEC engineers basically used radix40 as the basis for a compressed
character set which included the alphabet, the numerals, the space, and
three other special characters (which varied by machine). They called it
"RAD50", because in that era DEC were into octal arithmetic and every-
thing was in three-bit groups.  It worked - they packed three letters
into every 16 bits (40 x 40 x 40 = 64000), but the glaring problem was
that it didn't work for anything but filenames - the character set was
too small. There were also performance issues. Using non-binary bases
for character sets is not kind to ALUs; lots of division, modulus and
multiplication are involved.

Those who designed UTF-8 to represent Unicode in a flexible and fool-
proof way had a similar problem.  They decided on an approach in which
all transformations could use bit-shifting instead of divide and multi-
ply. We have done the same, which implies, of course, sticking to binary
bases and radices.

DISCUSSION

The best compression methods seek out redundancy in text - but in order
to do that, the analyzer needs a sufficiently large sample, which some
experts have determined needs to exceed 800 bytes for random text.  The
most elegant solutions generate dictionaries on-the-fly, requiring only
one pass through the data.  If this method does not serve, then the best
alternative is to make some assumptions about the data before it is ever
seen, perhaps even restrict the universe of permitted values, and then
dive right into a compression procedure from the very first byte.

UTF-8 solved many encoding problems - backward compatibility with ASCII
being the most important, but no less important is the ability to
recover from a bad byte or sequence error, to skip illegal segments
which may have come from some other Unicode encoding scheme, and so on.
But the recognition that an algorithm cannot be arrogantly wasteful of
CPU cycles is what has made it possible to utilize it without having to
worry about the cost.

IMPLEMENTATION

RadX is a useful combination of Radix-32/64 compression. The data is
primarily stored in Radix-32, which allows bit-shifting instead of divi-
ding/multiplying to greatly simplify computation. This is combined with
a check for double characters, which can be encoded effectively in 4
bits.  Other ASCII characters are stored in 6 bits; UTF-8 characters are
reduced to bare Unicode and stored in 24 bits maximum.  A series of zero
bytes is used for padding.

As the input string is scanned from left to right, all disallowed Uni-
code ranges are ignored.  Control characters are treated as spaces, and
all spaces consolidated.  If the character is UTF-8, the Unicode page
number is simply substituted for pages 00 to 0F.  For codes from U+0080
to U+0FFF, only the last 8 bits need to be added, so an extra byte is
used. For U+1000 onwards, two extra bytes are encoded. For safety,
certain bit patterns are detected and skipped.

If the character is not UTF-8, then it is simple ASCII - and Radix-32