On 08/02/2026 10:27 AM, Ross Finlayson wrote:[ viswath-charmaigne-readme.txt ]On 07/31/2026 05:03 PM, Ross Finlayson wrote:>On 07/31/2026 12:55 PM, Ross Finlayson wrote:>On 07/30/2026 07:05 AM, Ross Finlayson wrote:>On 07/30/2026 06:49 AM, Ross Finlayson wrote:>On 07/27/2026 11:45 AM, Ross Finlayson wrote:>On 07/27/2026 11:44 AM, Ross Finlayson wrote:>On 07/27/2026 11:43 AM, Ross Finlayson wrote:Hello, here I'll post some design notes and a panel discussion>
with
some
chat-bots about making some sense of the "vector-wide scalar word"
and "character machines", on commodity hardware about ubiquitous
operations.
>
>
It's considered at least tangentially relevant to comp.lang.c and
comp.lang.c++ because for example text is ubiquitous and the
targets
would be low-level, while the higher-level languages would have a
same sort of patternry, and for example that libc and cstdlib are
standard, and as with regards to POSIX and Unicode and so on.
>
Please feel free to excuse or ignore, or comment as freely.
>
Thanks for reading.
>
>
[ viswath-charmaigne.txt ]
>
>
>
>
>
>
Vector-wide scalar-word character-machines ([DRAFT])
For Viswath and Charmaigne, whoever they may be
Section: Abstract
Modern commodity computer processors have in the cores of their CPUs
both general-purpose registers and vector registers, with a usual
purpose for the parallel processing of picture elements in multimedia,
while the task of computers is often algorithm on text and strings,
which is essentially serial in encounter order of characters in text.
The vector-wide scalar-word approach identifies a common subset of
packed and vector operations in modern commodity 64-bit CPUs that are
alignable and operable byte-wise, for a vector of bytes, then defines
algorithm to treat the vector as a scalar for arithmetic, logic, and
comparison, to make for text algorithms on character data in ubiquitous
and various character sets their encodings. This provides linear speedup
on the order of 16 of many common text algorithms, with the existing
infrastructure.
Section: Overview
Algorithms on text and strings are often defined according to serial
character access, with regards to formal languages, formal automata, and
formal methods, in accounts of right and linear and regular expressions,
and context-free and context-sensitive grammars, and in accounts of
substring-match, and the results of recognizers and evaluators,
according to expressions and grammars, finding and matching
representatives and productions. The model of computation of these
definitions is often exactly according to the serial.
Operations on the ubiquitous commodity 64-bit CPU core, in the cores of
the modern many-core central-processing units in a usual setting of
clustering and virtualization or distributed algorithms of the
many-core, have internal their cores vector-processing units integral to
the central-processing units, that can operate on multiple data elements
at a time in a model of computation of SIMD,
single-instruction-multiple-data, providing a model of computation
that is parallel.
The commodity cores among various vendors and various instruction set
architectures have a common functionality with regards to the operations
on data on the registers, the central memories, of the cores, for the
treatment of vectors as of a sequence of bytes, then the operations that
are the logical and arithmetic and comparison naturally are super-scalar
across the word and act as a single instruction, thus the "vector-wide
scalar-word" ("VWSW") makes for that algorithm defined under this
profile is modeled as computation by the ubiquitous cores. Then, the
various vendors have common limits of the word-size and register-count,
in multiples of 128-bit word-size and 16-many register-count, then that
the register file can be considered as a collection of 128-bit wide x
16-many blocks, of the vector-registers ("v-registers") of
vector-register blocks or "vr-blocks", within a virtual vector-register
block ("vvr-block").
Thusly many what are serial algorithms, thus limited by serial access in
time, may be developed as parallelized algorithms, when sequences and
subsequences upon the v-registers, their instructions are single and
compute for each element in the vector-register in one instruction. This
is the "vector-wide scalar-word", for the byte-wise organization of
views and windows of sub-sequences processed within the vector units.
Then, this is called "Viswath", which is a proper personal name of
Indian origin with phonetic resonance with "VWSW".
Algorithm on text data as character data in byte-sequences then can
be defined to be made from operations according to the vector-wide
scalar-word, then to result linear speedup of accounts of "findings"
and "matchings". Text data as character data in octet-sequences
or byte-sequences has various character-sets and
character-set-encodings. These include standards like ASCII and Unicode.
and encodings like UTF-8, UTF-16, and UTF-32, which define the
interpretation of byte-sequences as character data. These character sets
are variously single-byte (or "unibyte") and multi-byte, and the
encodings are variously fixed-encodings and variable-encodings,
where the numerical identifiers of the characters, or codepoints, in the
character sets are from a bounded range, and the numerical identifiers
of the encoded characters, also codepoints, are also from a bounded
range. The algorithm works on the encoded characters in their natural
layout, i.e., as contiguous byte sequences according to their layout in
memory.
Then, character-classes introduce properties of kinds of characters,
according to their categories and origins and usages, for example
letters, digits, symbols, punctuation, whitespace, and so on.
Then "findings" are algorithm what uses the operations
of arithmetic, binary-logic, and comparison, which are single
instructions, to compute indicators and counts, which model the
existence of sameness and difference or membership or collection,
accounts of relation, of sequences of characters, according to
character-classes, and character-ranges. The "matchings" then are as of
according to contexts of syntax and semantics or structure, results of
evaluation, of recognizers and evaluators, about expressions and grammars.
Besides employing the vector registers for parallel/packed operation,
another usual pragma of modern ubiquitous commodity cores is
to design algorithm that avoids "stalls" which result from memory
accesses, unpredictable "branches" which result from essentially
random conditions, and "calls" which result from passing control
to other parts of the flow-graph in the usual account of calling
conventions and the model of computation. Then, "faults" are another
account which represents both logical faults in the core or exit in
error from the routine. Thus, the "Stall/Branch/Call/Fault-less"
is an ideal of implementation, since it results a systolic routine,
and the cores naturally are fastest when the code is so organized,
where the costs of a Stall S and a Branch B and Call C is basically
according to S < B < C < F, each of which is greater in cost than the
"SBCF-less", or "SBC-less" when there is no possible fault in the
algorithm. Then, the "SBC-less" is an ideal, where the "SBC-free" is an
explicit account of algorithm meeting the ideal of being SBC-less. This
can define "O(1)" or constant-time and constant-space.
Then, a "standard algorithm" is defined for character data generally,
that results making "findings" for an input text and an input pattern,
using the operations on the chip, toward a "SBCF-less"
instruction listing, on the vector-wide-scalar-word, that in modern
ubiquitous commodity processors, thoroughly employs the cores'
internal units, to result "findings" on sequences of input text and
input patterns, then that "standard procedures" operate on the
results of "findings" to make results of "matchings", usual the
general-purpose machinery of the core with memory/branches/calls
that result the evaluations of the recognizers and expressions and
grammars.
Section: Glossary
The glossary isn't alphabetical, instead conceptual, with an idea
to introduce the terms as they would be encountered in definition.
The definitions as they are are usually conventional, meaning with
their common and well-known meaning. The use of gerunds like
"findings" and "matchings" is to reflect that those are nouns, of
the results of the actions of verbs. Otherwise the terms are nouns.
value
action
result
process
input
output
event
condition
predicate
evaluation
indicator
accepter
rejecter
resources
time
space
complexity
simplicity
correctness
performance
scalar
array
index
vector
layout
byte
bit
nybble
word
work
byte-wise
bit-wise
word-wise
SIMD
SWAR
location
width
extent
offset
relative-offset
Start-of-Input
End-of-Input
processor
control-flow
g-register: a general-purpose or general-auxiliary register
v-register: a vector-register in vector-wide-scalar-word
block: polydimensional array with offset indices
m-block: a block of memory
cd-block: a block of code & data
vr-block: a block of vector-registers
vv-register: a "virtual" v-register
vvr-block: a "virtual" block of vr-blocks
Stall: waiting for an access to memory
Branch: conditional jump of control-flow
Call: passing control-flow
Fault: an error condition in the operation
SBC-less: the ideal of absence of Stall/Branch/Call
SBC-free: the state of being SBC-less
SBCF-less: the ideal of absence of Stall/Branch/Call/Fault
SBCF-free: the state of being SBCF-less
AND: the word-wise logical operation, usually '&'
IOR: the logical operation, inclusive OR, usually '|'
XOR: the logical operation, exclusive OR, usually '^'
NOT: the logical operation, inverses bits, usually '~'
SHIFT: the word-wise operation, shifts byte-wise right or left
ROTATE: the word-wise operation, rotates byte-wise right or left
CMP: the comparison operation, for equality
ACC: the accumulator operation, like addition
LOAD: the operation to copy a value from memory to a register
STORE: the operation to copy a value from a register to memory
COPY: the operation to copy a value from a register to a register
EXTRACT: the operation to extract a scalar from a vector at an offset
INSERT: the operation to insert a scalar into a vector at an offset
indicator-sequence: a sequence of bits denoting indicators for offsets
accumulator-sequence: a sequence of sums denoting tallies for offsets
algorithm
procedure
routine
function
language
letter
character
codepoint
storage-element, "stel"
string
substring
character-set
character-encoding
character-codepoint
character-class
character-property
single-byte-character-set
multi-byte-character-set
fixed-length-character-encoding
variable-length-character-encoding
endianness
uni-char: a character with one storage-element
vari-char: a character with variably-many storage-elements
ASCII
Microsoft Windows codepage
ISO-8859
UCS2
Unicode
UTF-8
UTF-16
UTF-32
NUL
Byte-Order-Marker
leading byte
trailing bytes
high surrogate
low surrogate
window: a bounded view of a work or word, of bytes or characters
avast/beyond: before/after the window's bound
ledge: zero or one beyond the window bounds
empty-string: a degenerate string with no characters and no width
text: a string the body
pattern: from string-matching a substring to match, here a layout that
results
pattern-element, "patel"
input-text
input-pattern
char-properties: a byte with bit-flags indicating properties
char-predicates: a byte of bit-flags indicating predicates
char-codepoints: the bytes of a character
char-rangepoints: a pair of upper and lower bounds of range of bytes of
a character
finding: arithmetic/logic that results indicators
matching: relating findings their indicators to expressions that results
evaluations
matches
expressions
grammars
representatives
productions
filtering: composition of finding logically by indicators and conditions
made-match: a definite positive matching
mis-match: a definite negative matching
maybe-match: an ambiguous potential matching
striding: a regular offset-increment, for example 1, 2, K
straddling: when a codepoint crosses words
splitting: when a codepoint is split between words
stitching: re-assembling a codepoint that's split
After-Split
Afore-Stitch
Behind-Split
Before-Stitch
smashing: with un-smashing, accounting for codepoint stride
smearing: with un-smearing, account for the variable-length codepoints
squashing: in smashing, fitting into more
stuffing: in un-smashing, fitting into less
squeezing: in smearing, aligning more bytes into less bytes
spreading: in smearing, aligning less bytes into more bytes
find-first: finding through much data for unlikely pattern
find-long: finding through much data the longest pattern
find-next: finding from an offset among alternatives
find-plex: finding from an offset multiple alternatives
sa-free1: standard algorithm for find-first
sa-star: standard algorithm for find-lone
anchored: making findings from a fixed offset
drifting: making findings across a region
sa-fixed: matching a fixed string starting at an anchor
sa-drift: matching each occurrence of a fixed string across a word
standard algorithm
standard procedure
standard maintenance
standard layout
Section: Constants and Variables
The constants are integers and usually unsigned integers.
The values of width are in units of bytes, and offsets and
extents are unsigned integers, while relative-offsets are
signed integers.
The usual units of size are bytes (octets, 8-bits) and bits,
with upper-case for bytes and lower-case for bits.
B, b: units of bytes and bits
When B is used as a unit, it is always prefixed with the
quantity, to disambiguate it later from "A & B" as one avast/beyond
the left and right endpoints of a word.
The widths and offsets are mostly in bytes
W: width of word of v-register (16B, 128b)
K: width of a pattern
N: width of an input text
O: offset
L & R: left and right relative-offsets
A & B: ledge avast/beyond L and R
There are regular variable names.
C: array of characters C for each character c
P: array of pattern-elements P for each pattern-element p
S: string S
Z: window Z
Section: Vector Model
The build targets under consideration are the modern commodity
ubquitous 64-bit processors with general-purpose and vector units,
commonly found in personal computers and telephones and servers,
from various vendors including Intel/AMD and ARM. For quite some
time or a decade or more, these processors' vector units include
multiples of 128-bit wide vector registers, and multiples of 16-many
vector registers (in the instruction set architecture). The vector
registers their 128-bit wide segments, called v-registers, in a group
of 16-many as 16-deep is called a vector-register block, or vr-block.
The targets have an integral number of these vr-blocks, in what's
considered a virtual vr-block, or vvr-block.
The properties of a v-register are that it is not a general-purpose or
g-register, where the targets have 8-many to 32-many g-registers with
64-bit width and the gamut of instructions. The v-register is considered
to only have a subset of the instructions actually available, that the
v-registers may be considered a vector of 8-bit bytes, interpreted as
unsigned integers.
The v-register is 16B = 128b wide, and called a word or vector,
with width W = 16B and array variable V subscripted 0-15.
These are the available instructions of v-registers.
logic: AND IOR XOR NOT, bit-wise, 16B at a time
arithmetic: ADD/ACC, byte-wise, 16B at a time
shifting and rotating: SHIFT ROTATE, word-wise, byte-wise, 0-many to 15-many
comparison: CMP, byte-wise, 16B at a time
comparison-transitive: CMPTRANS, across bytes when 2-4 bytes indicate
ordering
These are the instructions between the v-registers and main memory.
Loads and stores are assumed to be aligned to 16B.
loading: LOAD, word-wise, 16B = 128b at a time
storing: STORE, word-wise, 16B = 128b at a time
These are the instructions between the v-registers and g-registers,
that take the values from a v-register, for one of two purposes:
to gather the high bits of each byte of V as a bit sequence of
indicators and copy off to a g-register, or to collate the sums/tallies
in each byte of a v-register, and given a third operand K in 0-15,
compute the locations where either a byte's value is greater-than the
previous value, or the offset is an even multiple of K from a previous
byte's value that's equal to the byte's value.
indicator-sequence: COPYINDICATOR: for a byte-sequence in V
of values 0x00 or 0xFF, a bit-sequence of indicators of each like PMOVMSKB
accumulator-sequence: COPYPROFILE: when a bit-sequence of indicators
would be ambiguous, from a running tally of partial sums, a profile
under the modulus length K of the pattern, then results a bit-sequence
of indicators
Then, when the processors have vectors longer than 128b, they are in
multiples of 128b, like 256b or 512b or higher, these being called
vv-registers,
then there are instructions to insert and extract v-registers to and
from vv-registers.
insert: INSERT, inserts a 128-bit v-register word into a >= 128b vv-register
extract: EXTRACT, extracts a 128-bit v-register word from a >= 128b
vv-register
These instructions are either direct operations according to the
instruction set architecture ISA, called "built-in", or "synthesized" of
other built-in operations as multiple instructions. Then, the vector
operations are a common subset of available functionality, oriented
about the word-wise and byte-wise, while the bit-wise, is not generally
available on the vector registers, which are generally organized
according to 16-bit "words", in the usual meaning
of assembler's 16-bit words, 32-bit double-words or dwords, 64-bit
quad-words or qwords, and 128-bit double-quad-words or dq-words, not
8-bit bytes, here in the 128-bit v-register "words", called "words" (or
"v-words".
The instructions generally have a source operand and destination
operand. The CMPTRANS and COPYPROFILE instructions are more complicated
than the other instructions, with a third operand and being horizontal
between words, when for example they are specialized to the target or
synthesized in the g-registers. The INSERT and EXTRACT instructions are
complicated with a third operation about the vvr-block index of the
vr-block, and the general account of the vr-blocks in the vvr-block.
The INSERT and EXTRACT instructions involve the model of the
virtual-vr-block, since there aren't separate/independent 128b-wide
vector units in the 256b, 384b, 512b, ..., wider vector registers,
instead the 128b double-quad-words are aliased into the wider registers,
then that INSERT and EXTRACT indicate the offset of the 128b word
(double-quad-word) in the wider or vv-register.
Then, while this is yet a draft of the design ([DRAFT]), the above is
considered to outline the vector model of "Viswath: byte-wise",
vis-a-vis, "Viswath: bit-wise", or in terms of "Viswath and Bonnie:
byte-wise" or "Viswath and Bletchley: bit-wise".
Section: Process Model
The layers of operation in the machine are defined in terms
of "algorithm", "procedure", "routine", and "function" These
of course are common terms in many programming languages,
here that in this context are separated these as with regards to
"interfaces and internals".
The process model is on the commodity chip architecture.
These processors have features that encourage code that,
while logically consistent for its function, avoids states
not aligned with the super-scalar pipelined cached architecture
of the chips. These are "Stalls", when a referenced memory, loads
and stores, causes latency, "Branches" when branch mis-prediction
on essentially random branches cause pipeline-evictions,
"Calls" when the flow-of-control is passed through the operating
system to what would be external functions, and "Faults"
when logical or access violations cause errors. Then, the
"SBCF-less" is an ideal, of organization of routine, that aligns
with the architecture and direction, for efficient operation,
where of course loads/stores and conditional-logic and
function-calls are ideals themselves for their purpose.
There's a general consideration that the costs of Stall, Branch,
Call, Fault are S < B < C < F. Then, when code is Fault-less, then
here is for the SBC-less. When code has no logically possible
stalls, branches, calls, or faults, then it's "SBCF-free".
The "algorithm" is the operation on the v-registers the v-block, where
the algorithm is to be SBC-less. The algorithm is defined
by "standard algorithms", that given contents of the v-registers
in the vr-block, result exactly the SBC-less operation, while
interacting with the "procedures" then to be defined, via
destination g-register conventions. The "algorithm" is
invoked by "procedures".
The "procedure" is the operation on the g-registers or
general-purpose, that result implementing the "standard
algorithms" and "standard procedures", with the goals
of the SBC-less, and that the cases where there are stalls
or branches or calls necessarily in the "standard algorithm",
that it's via "standard procedures". Thusly, procedures are
the interface to the algorithm, which is internal to procedures.
Procedures are considered internal their own calling convention,
or to have no calling convention internally.
The "routine" then is for the various accounts of configuring
the "procedures", and invokes the procedures. The routine
might have its own or usual calling conventions.
The "function" then is the external interface, usually with
the idea of exported library symbols their ordinals in
static or dynamic libraries, with the usual meaning of "function"
in C-style organization of object files and conventions of linking
and calling.
Section: Character Model
Textual data or text is in the organization of computer data: of an
"uninterpreted octet-sequence", or a sequence of bits indexed by offset
into 8-bit bytes, then the interpretation of the "binary" data as "text"
data.
Textual data is ubiquitously organized in binary as octet-sequence or
bytes, single-byte or multi-byte, representing unsigned integers, these
being "codepoints" in the space of assignments of letters and symbols,
from language or codes, the character-set. Then, since the alphabets of
these languages grew beyond the original limits of the single-byte,
later to fill multiple bytes, then grew together in a world where most
of the text was organized in single-bytes, then various encodings
into the variable-byte encodings, these then call character-set-encodings.
The computer type that represents an octet is called a "byte",
and is the least addressable unit in memory, the computer data type that
represents a character is called a "char", and is often mostly defined
in C-style libraries to be a byte, vis-a-vis "wchar" a wide-character
with two bytes, or, often enough "Character" in the higher-level or
later languages, with two-bytes or four-bytes. Here in this model, the
"char" type doesn't have a fixed width, it has an offset and an extent
in an array of bytes, called "char-start" and "char-length", the offset
and extent, and called character or char.
For a given byte-sequence, there are offsets the index for each byte,
then as character data, a char-sequence, there are offsets the index
for each character. A byte-sequence is meant to reflect an array
of character with ordinal indices, a char-sequence is meant to reflect
an array of characters with ordinal indices.
The two main standards for textual data are ASCII, which define
characters for the codepoints 0-127 in most character-sets in wide use
today, and Unicode, which is a comprehensive global effort to make every
letter and symbol in regular usage in text, and as well other symbols
and codes describing writing systems, into one space of codepoints.
Circa 2026, the Unicode assigned space is about 2^21-many characters,
vis-a-vis the 2^7 characters assigned in ASCII.
ASCII characters fit in one byte, and even 7-bits in one 8b byte,
traditionally called "7-bit clean", while Unicode assignment followed
parallel efforts in the multi-byte for what are called "wide
characters", as fit in 16-bits, with 2^16 many codepoints.
As the space grew past 2^16-many, and also as various later symbols, for
example "emoticons" or "emoji", entered regular usage and were assigned
values beyond 2^16, then as both 8-bit characters, which is the default
in most standard libraries after the C-style standard library of program
functions, and 16-bit wide characters, which
were first widely implemented on consumer operating systems, were
out-grown, and as well the space of those codepoints is largely un-used
since most text for source text and data is in printable ASCII, then
variable-byte encodings emerged and were adopted where that the two main
character-set-encodings under consideration
are UTF-8, and UTF-16, which have a minimum of one-byte and two-bytes
respectively, and range of 1-4 1B elements 1-2 2B elements respectively,
to represent all the characters in Unicode as are in UTF-32, which is 4B
for each character, with padding zeros for
the un-used bytes of the character.
The "character model" of the "character machine", then, is that the
native layout of the encodings, is single-byte or multi-byte, and
fixed-length or variable-length. The operation of the "character
machine", then, establishes to maintain both byte and character offsets,
and then for the purpose of the character machine: to find matching
properties between an input-text of text and an input-pattern of
laid-out predicates of text, using the vector model, according to the
character model.
While planning to organize about various encodings, yet the corpus,
where the corpus is all the text in all the files, the corpus of source
text and data is overwhelmingly ASCII, while, commonly UTF-8. In many
settings, the corpus is overwhelmingly UCS2, while variously UTF-16.
There are many other character-sets and character-set-encodings in
historical and wide use, here that various standards of the operating
systems and information interchange has a variety of single-byte
character sets, usually for European languages, and a variety of
multi-byte and variable-byte character sets and encodings, usually for
the Asian languages. The "character machine" then is configured to
operate on a given character set and character-set encoding, and thusly
configurable, while the association and detection and inspection of
binary data for its character set and character set encoding, is
considered an invariant or parameter to this "character machine",
which then is designed to run algorithms of finding and matching,
according to input-text and input-pattern, in the character set and
encoding for which it's configured.
The configuration of then machine then is for single-byte,
or double-byte, then that the single-byte configuration handles
the variable-length UTF-8, and the double-byte configuration handles
the variable-length UTF-16, where the storage-elements are 16b,
8-many in the 16B v-register.
Handling character data then, the variable-length, when the storage
elements are bytes, and the character offsets are thusly
greater-than-or-equal to the byte offsets, then is the idea of what
these designs intend to fulfill.
Section: Character Classes and Patterns
Where text is thusly a sequence and arrangement of symbols or letters
from the languages, then the fundamental description of a "pattern" of
an individual "character" is a "character class". A character class is a
relation from one class to many characters, representing a collection of
characters, and characters have relations to many classes, for example a
universal class and an empty class, yet character classes are usually
very specific to the interpretation of the character its purpose and
meaning.
A "pattern" then is a sequence of bytes, for a pattern P, the pattern
will be according to "predicates for properties" and "rangepoints for
codepoints".
In these character machines then, the model of operation is that the
byte-wise data is loaded into a vector word, then for each byte in the
vector word, is associated a byte representing the "main class", the
main character class.
The main class is an octet or 8b byte, and in this character machine
model, or Charmaigne, the main class is partitioned two 4b nybbles. Each
nybble has four bits, and each bit by its bit-offset in the nybble,
indicates membership in a particular class. The character class after
the main class indicates a closed category of classes, any character
falls in exactly one class, thus that the relation
is one-to-many class-to-character, and many-to-one character-to class.
The main class high nybble thusly is, for each byte in the input-text,
one of alpha-numeric, puncutation, or whitespace, in ASCII, or "coded".
Then, the "coded" low nybble has four classes: NUL, BOM, cntrl, UTF.
The NUL character is zero, written '\0', it's the usual string
terminator in C-style strings, vis-a-vis Pascal-style strings, which are
length-prefixed. The BOM class is for the Byte-Order-Marker, in UCS,
it's a specific codepoint that indicates the Big-Endian or Little-Endian
endianness of UCS2 data.
Then, UTF is for both UTF-8 and UTF-16, indicating that it's the leading
or a trailing storage element for UTF-8, or, a high or low surrogate for
UTF-16.
Thusly, the main class conditions the logic of the machine for the
handling of the uni-char and vari-char elements.
Then, the low nybble for the other main classes, are organized to
reflect usual character classes.
alnum: upper lower zero whole
punct: inner outer joiner affix
white: nl space horz vert
coded: utf nul ctrl bom
After the main or primary class, then are secondary and optional
classes, again organized with high and low nybbles, hierarchical after
the main class with a standard definition of classes for source and data
text.
These character classes their encodings are then called "properties".
For each character in a pattern P, then for each "properties" byte,
there is a "predicates" byte, that by simple logic the findings will
compute any-match/all-match of the properties to the predicates, from
the pattern. Zero is never matched, and zero in the predicate means
"ignore".
The pattern has conditions, that indicate match-any or match-all
of the predicates, so that predicates can combine and pick the
character classes of the closed categories indicated by the properties.
Another way to specify character classes is "rangepoints" for
"codepoints", the pattern may have a pair of lower and upper rangepoints
to define a range of characters by the numeric value the codepoints,
then that defining a character class, where membership is defined by the
codepoint being in the rangepoints. Zero is never matched, and zero in
the rangepoints means "ignored".
The pattern has conditions, that indicate complement to
classes. The complement to a character class CC is as the
universal-class setminus the character-class, UC \ CC. The pattern
indicates whether to complement the predicate-defined class, to
complement the rangepoints-defined class, or complement the resulting
combined class.
Section: Input Layout
This then is for introducing the layout in the vr-block of the
v-registers of the character machine, of the input text, and input
pattern. The vr-block has 16-many v-registers, numbered 1 through 16.
vr-1: codepoints (bytes/storage-elements, contiguous as codepoints, text))
vr-2: properties main (text)
vr-3: properties secondary (text)
vr-4: properties tertiary (text)
vr-5: predicates main (pattern)
vr-6: predicates secondary (pattern)
vr-7: predicates tertiary (pattern)
vr-8: rangepoint-upper (pattern)
vr-9: rangepoint-lower (pattern)
vr-10: condition-flags (pattern)
vr-11: varibyte-only: codepoint varibyte indices (text)
vr-12: varibyte-only: rangepoint varibyte indices (nybble
bytes-encountered, nybble bytes-remaining, pattern)
The registers marked "(text)" are the text itself and what's derived
from the input-text, then the registers marked "(pattern)" are the
values that
The output of the algorithm is copied to the g-registers or for the
procedure, while the algorithm works on the contents of the v-registers.
A usual account of the layout of the input by procedure loads the
input-text, and the input-data, independently.
Laying out the input-text is as procedure loads the input text,
loads or looks up the derived properties of the input text,
detects coded characters and their vari-byte indices, of
the v-registers marked "(text)".
Laying out the input-pattern is as procedure
detects coded characters in the rangepoints and their vari-byte indices,
loads the predicates, and loads the conditions.
Other v-registers in the v-block are reserved for use of procedure,
for the interactions with algorithm, and the interface with routine.
vr-13: maintenance (algorithm/procedure/routine written before processing)
vr-14: memo (algorithm/procedure/routine written after processing)
There are two considered constants that will be usual values
that are defaults.
vr-constant-zero
vr-constant-ones
Then the other registers considered in the vr-block are as for
constants and temporaries.
vr-temporary
The virtual-vr-block or vvr-block requires a reserved register
for insert/extract of the vr-block in the vvr-block.
vr-16: virtual-alias-temporary
This is that any sort of load/store of a v-register in a vr-block,
is abstractly of an aliased virtual v-register in a vvr-block, since
the wider registers (256b, 512b, ...) alias 128b-wide v-registers
of the vr-block into its layout in the vvr-block.
Section: Finding and Matching
The main operation of the character machine is "finding" then
"matching", where "finding" is that arithmetic computes value results in
the algorithm, then "matching" is that procedure evaluates the results
to make results and events of the results for expressions and grammars
according to the routines.
The "findings" are, given the input-text and input-pattern, computing
the indicators and offsets according to algorithm. The findings are
specifically constant-time and constant-space, and for the SBCF-free.
The "matchings" are, given the output indicators and offsets, according
to the "state-machines" of the evaluation of the expressions of the
recognizers/evaluators after accepters/rejecters of expressions for
matching and regular expressions and grammars, the matches and
representatives and productions.
The overall state-machine of the character machine is called "the
character machine", while "state-machines" reflect the routines
that results for functions, the evaluation of matches, expressions,
and grammars.
Design Notes ([SCRATCH])
Note: Carry Composition
About carry, which is the layout for data of the standard maintenance,
is the idea of "partial carry" or "composable carry", the idea being
that the vr-blocks are independent while run together lock-step whatever
vr-blocks are aliased together, is that the offsets and the like computed:
byte offset
char offset
and so on are the partial sums in relative offsets, then that those are
to be accumulated in various orders, where the vr-blocks in the
vvr-block have been allocated/scheduled in various orders and across
various "active" vr-blocks, alike lanes themselves, and "banks" of
vr-blocks, where the first 16-many are one bank and the second 16-many
the other bank, then that as the units have first one then two or more
vr-blocks in the vvr-blocks, in the wide and deeper, then to make for
the various findings into the works as they straddle and cross blocks,
across, and schedule and resolve blocks, down, that the standard
procedure is as of which of those to update, given results of matchings.
Or, this introduces "active lanes" and "active banks"
in the vvr-block.
Then, the offsets are to be as with regards to Stride S,
and Char C, then those are to be "composable carry" as
they are "relative offsets", about then that parity and
the modulus, or for stride, then that the machine on
a block knows the offsets, then that the usual outputs
are first the findings of the characters in the sequence
of storage-elements, then that the characters and findings
for matches belong variously to the previous or next element,
when there is straddling.
S: stride (storage-elements, eg 1, 2, 4 bytes)
M: modulus (modulus left / modulus right)
So, the first sort of bit-sequence that's about from any standard
algorithm, is for the byte-starts the char-starts, where it's figured
that the output is always about the bytes as storage-element, or as with
regards to storage-elements and characters, what those are, for each of
the 16-bytes as usual, or as with regards to making those being
storage-element offsets, since, then they'll fit for 64-characters
worth, in 64-bits.
S1: 16-many storage-elements, <= 16-many characters
S2: 8-many storage-elements, <= 8-many characters
S4: 4-many storage-elements, <= 4-many characters
Then, it's figured that how those fill the output, the bit-sequence of
storage-starts and char-starts, are according to that the entire machine
is parameterized by the multibyte its stride 1, 2, 4, then that when
accumulating the starts and runs, that the 64-bits is always for 64
characters, since it will always be for less-than-or-equal to 64
storage-elements.
Then, the pattern length is assumed to be less-than or much-less-than
the input text, for example for fail-fast where it's not, while, the
results of evaluating expressions, since patterns are basically
un-decomposable sub-expressions, gets into the unbounded. The point here
is that the pattern as either un-decomposable or of fungible primitive
elements, gets its offsets and so on, for the smashing and smearing,
computed once for the pattern, absolute for the pattern, while, over the
input-text, is the "composably carry" the block-wise, is over the
stride-wise, or for various accounts of "stride" and the "modular", to
result where when for a sequence of blocks they're even and 0 modulo the
"staggers", as they are, makes for "stagger" for "stride".
Start-of-Input: off_t
Start-of-Input-Inset: off_t % W
Start-of-Input-Aligned: off_t - Start-of-Input-Inset
End-of-Input: off_t
End-of-Input-Inset: W - (off_t % W)
End-of-Input-Aligned: off_t + End-of-Input-Inset
Then, the idea is that all the offsets are relative the start-of-input,
while the loads being aligned would result that there's the stagger
as it were, or "lurch", where it's figured that aligned-loads (to 16B =
128b) are always safe and un-aligned-loads are potentially unsafe, since
all the operating systems have safe aligned loads of any accessible
protected memory page by PAGE_SIZE, that's >= 512B.
There's what are intermediate and running results internally,
then what's potentially surface, and about the bounded resources,
and the unbounded resources, and memoization in the partial,
about a general account of what out of the vr-block gets serialized,
and thusly to identify what sort of organization results the constant
limits, and the growth limits, in the intermediate, and the running,
the bounds.
Then, since storage-elements (bytes here, then for that storage-elements
work out same) and character-elements, the byte-offsets and char-starts,
or storage-offsets and char-starts, have that character width is g.t.e.
storage-element width, then is for a usual account of an "index file".
The index-file is an account of usually enough a list of offsets, or
differential or incremental offsets, to markers/separators in the file,
like line-endings for line-oriented text-data.
So, a usual idea of building the index, is here that there's always
the variable-length characters, then among those, particular indicators,
that the index then to the separators, makes for hierarchically the
index to the substrate.
Then, about making a model of a string in the character machine,
with byte and char iterators, or iterating, or index-accessing,
is a different account than findings, since it's figured that the
findings simply "return" (emit) byte-offsets of char-starts, and the
byte-extents of the matching-ends, then that the application has its own
account of the encoding of the data, or agnostic.
offset
extent
offset-lower
offset-upper
Then, the format of the indicator-sequences and accumulator-sequences,
then indicator-sequences derived from accumulator-sequences, is that
then the translation and interpretation to offsets, is that each
vr-block its corresponding input-text v-register word, has a natural
serial ordinal, from the start-of-input (aligned).
Then, "N" might be for "Natural", or natural ordinal, of the words,
where since the accounts for O(N) and the like are in terms of W's
stride, then though that usually enough that O(N) is for the input in
bytes, correspondingly characters, that the byte-count >= char-count,
while word-count >= byte-count, and is in fact a constant, that O(cN) ~
O(N).
Then, the account after the scheduling, is that each word of input-text,
is associated with an ordinal N, and a pattern P (an "instance
identifier" of the instance of the findings/matchings of a decomposable
or "molecular" pattern), then about the context and the carry, between N
and P.
Then, two sorts concepts alike "relative and absolute" and "atomic
and molecular" suggest themselves, then, for findings and matchings,
is about the "decomposable and indecomposable", and "degenerate
and non-degenerate", basically for identifying that while the
character-set-decoding process itself involves "findings" and
"matchings", making findings that generate the varibyte considerations,
that those are "atomic" in the sense of that characters have no split
meaning, they're "non-decomposable", while, the composition in patterns
is character-wise, they're "non-degenerate", while the bytes or
storage-elements as "degenerate" are yet "absolute".
Then, the carry-layout gets involved the Left and Right or L and R,
of both the storage-elements and characters, of both the input-text and
input-pattern.
The varibite in the procedures and algorithm, is that the decoding
aspect of "coded"-class bytes (storage-elements), is "horizontal",
it involves that well-formed UTF-8/UTF-16 has for the leading element
(leading element of UTF-8, high/low surrogate of UTF-16 in endianness)
then that it's derivable the bytes-encountered/bytes-remaining
(storage-elements or "sels" or "stels" encountered and remaining
respectively), about the partial elements, not necessarily the summary
elements, yet to make derive-able the summary elements, with the point
being that the tractability and summability is on the partial sums and
relative offsets internal to the algorithm/procedure, so that it's
general enough to support general association of the values from
multiple axes.
So, for the carry-state from the previous word, one aspect that's
reducible is the computation of the CMPTRANS, where, all that's
necessary is a bit indicating for the previously-compared bytes/stels,
gt/lt respectively, one for the upper and one for the lower bound. The
properties/predicates have for the stels and chars that those are copies
among the stels, so, there's no need to carry those,
CARRY_CMPTRANS_UPPER:1
CARRY_CMPTRANS_LOWER:1
Then, the idea is that that forms part of the "maintenance" v-register,
since then the standard procedure that makes CMPTRANS, will employ
that bit to indicate how to result the CMP on the codepoint, and that
the account of characters that straddle words, is that they're deferred
their results until the next word, where the overall operation would
be determinate, vis-a-vis that the initial segment indicates the
short-circuit AND logic that it's determinate.
So, the account of finding is byte-offsets of char-offset of matching to
the pattern-outline. Then, there's first the finding of the char-offsets
as matching the universal-class or .*, then also, there's what was the
remainder of the previous word, so that thusly it can be determined what
are made/mis/maybe-matches.
indicator-sequence-1: char-ends: stel-offsets that mark/indicate
complete characters
indicator-sequence-2: char-starts: stel-offsets that mark/indicate found
pattern matches
Then it's figured that those are W/S-bits wide, eg, W = 16, S = 1 ->
16B/1B = 16-bits wide
for single-byte, S = 2 -> 16B/1B = 8-bits, ..., then the idea is that
for the patterns,
then, they'll generally be working on 64-bits at a time, in the space of
characters.
So, the composable-carry and ownership and transfer logic is being
figured out, first for CMPTRANS and about then the IST/ISST/... aspects
of procedure in the algorithm, and about how to result for the "atomic
findings" and "molecular findings", then what is to result that the
matchings have a simplified sort of account of their evaluation of
the bit-sequences, 64-many at a time, char-wise.
Then the vr-maintenance register is with the idea that maintenance
occurs in the layout _before_ processing the block, while memo in the
vr-memo occurs _after_ processing the block, with the standard algorithm
/ standard procedures. Then it's figured that half of the vr-maintenance
/vr-memo registers belong to the algorithm/procedure, and half to the
procedure/routine.
Note: SIMD/SWAR and Fallback Reference
With the vvr-block and the vr-block about 16B-wide and 16-many deep,
then the general-purpose available for fallback is about 8B-wide and
4-many deep, general-purpose registers or as with regards to MMX
registers the 8B-wide and 8-many deep, then the idea that for the
"virtual vr-block" would be the "simulated virtual vr-block", or
svvr-block for SWAR, then about that the layout would be the same, yet
it would be assembling it in memory and there would be loads and stores
involved and not be SBC-less, while being BC-less, though ensuring that
the same behavior is available in a model of a high-level language, then
of the surrounding machinery about the patterns and for the routines in
the higher-level language, and simulating the procedures
and algorithm, in the general-purpose.
| Date | Sujet | # | Auteur | |
| 30 Jul 26 |  Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 8 | Ross Finlayson | |
| 30 Jul 26 |  Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 3 | Keith Thompson | |
| 31 Jul 26 |   Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 2 | Ross Finlayson | |
| 31 Jul 26 |   Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 1 | Ross Finlayson | |
| 31 Jul 26 | Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 4 | Ross Finlayson | |
| 4 Aug 26 | Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 3 | Ross Finlayson | |
| 6 Aug 26 | Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 2 | Ross Finlayson | |
| 6 Aug 26 | Re: Viswath & Charmaigne (vector-wide scalar-word and character machines) | 1 | Chris M. Thomasson |
Les messages affichés proviennent d'usenet.