niplav

creator: niplav, created: 2019-04-24, modified: 2023-06-22, language: english, standing: completed, significance: 4, confidence: doable

Pipelines are an
integral a part of the Unix working system. They arrive in numerous
variants (FIFOs and anonymous
pipes) and have many
purposes. Right here I present the way to abuse easy textual content information and unnamed
pipes to create cycles of knowledge stream.

A pipe ring has the next construction:

$ echo init >a
$ tail -f a | [filters] >>a

Normally, a comprises some initialization values. These initialization
values are then written into the pipeline, reworked by the filters,
and concatenated to the file. tail -f then reads these new traces from
the file within the order that they had been generated, and new knowledge is produced
by the filters.

Fill Disk

The only pipe ring makes use of no filters in any respect:

$ echo take a look at >a
$ tail -f a >>a

It merely fills the disk with a file containing the road “take a look at”.

Stop Ring

To cease the unconstrained use of laborious disk reminiscence, one can use sed:

$ echo take a look at >a
$ tail -f a | stdbuf -oL sed '100q' >>a
$ wc -l a
101

stdbuf is required as a result of on most system, the byte streams flowing by means of
pipes are buffered. Which means that if the command is tail -f a | sed
'100q' >>a as an alternative, sed consumes all enter, writes to the buffered
output (which has often a measurement better than the size of the road,
on my system it’s #outline BUFSIZ 1024). bufsiz units the output to line
mode, which permits the sed output to be propagated directly.

MU

In his e book “Gödel, Escher, Bach: An Everlasting Golden Braid” Douglas
Hofstadter describes a logical system referred to as MU:

The very first thing to say about our formal system—the MIU-system –
is that it makes use of solely three letters of the alphabet: M, I, U. That
signifies that the one strings of the MIU- system are strings that are
composed of these three letters.

— Douglas Hofstadter, “The MU-puzzle“ in “Gödel, Escher, Bach: An Eternal Golden Braid” p. 1, 1994

There’s a beginning string, and 4 guidelines to change this string:

RULE I: In the event you possess a string whose final letter is I, you’ll be able to add on a U on the finish.

By the way in which, if up so far you had not guessed it, a truth concerning the
that means of “string” is that the letters are in a hard and fast order. For instance,
MI and IM are two completely different strings. A string of symbols is not only a
“bag” of symbols, by which the order would not make any distinction.
Right here is the second rule:

RULE II: Suppose you’ve got Mx. Then chances are you’ll add Mxx to your assortment.

What I imply by that is proven beneath, in a couple of examples.

From MIU, chances are you’ll get MIUIU.
From MUM, chances are you’ll get MUMUM.
From MU, chances are you’ll get MUU.

So the letter ‘x’ within the rule merely stands for any string; however as soon as
you’ve got determined which string it stands for, it’s a must to stick together with your
selection (till you employ the rule once more, at which level chances are you’ll make a brand new
selection). Discover the third instance above. It reveals how, when you possess
MU, you’ll be able to add one other string to your assortment; however it’s a must to get
MU first! I wish to add one final remark concerning the letter ‘x’: it’s
not a part of the formal system in the identical method because the three letters ‘M’,
‘I’, and ‘U’ are. It’s helpful for us, although, to have some solution to discuss
typically about strings of the system, symbolically-and that’s the
perform of the ‘x’: to face for an arbitrary string. In the event you ever add
a string containing an ‘x’ to your “assortment”, you’ve got achieved one thing
fallacious, as a result of strings of the MIU-system by no means include “x” “s”!
Right here is the third rule:

RULE III: If III happens in one of many strings in your assortment, you
might make a brand new string with U instead of III.

Examples:

From UMIIIMU, you might make UMUMU.
From MIIII, you might make MIU (additionally MUI).
From IIMII, you’ll be able to’t get wherever utilizing this rule.
(The three I’s need to be consecutive.)
From MIII, make MU.

— Douglas Hofstadter, “The MU-puzzle“ in “Gödel, Escher, Bach: An Eternal Golden Braid” p. 2, 1994

Hofstadter poses a problem: beginning with the string “mi”, he asks
whether or not the string “mu” might be constructed.

An awk script implements the
4 guidelines:

/i$/ { print($0 "u") }
/^m/ { s=substr($0, 2); print("m" s s) }
/iii/ { i=cut up($0, a, "iii")-1; for(c=1; c<=i; c++) print(gensub("iii", "uu", c)) }
/uu/ { i=cut up($0, a, "uu")-1; for(c=1; c<=i; c++) print(gensub("uu", "", c)) }

One can now write an rc script to
implement a pipe ring that generates mu expressions.

#!/usr/bin/env rc

fn apr{
    stdbuf -oL awk '/i$/ { print($0 "u") }
        /^m/ { s=substr($0, 2); print("m" s s); }
        /iii/ { i=cut up($0, a, "iii")-1; for(c=1; c<=i; c++) print(gensub("iii", "uu", c)) }
        /uu/ { i=cut up($0, a, "uu")-1; for(c=1; c<=i; c++) print(gensub("uu", "", c)) }'
}

tail -f mu | apr | stdbuf -oL grep -E '^.{,80}$' | stdbuf -oL awk '!a[$0]++' >>mu

awk '!a[$0]++' is taken from
iridakos 2019
and filters out duplicate traces.
Additionally, stdbuf would not work with rc capabilities, so it must be written
instantly into the perform. grep is used to forestall extraordinarily lengthy
traces from forming by means of the repeated software of the primary rule.

Executing the script offers the specified outcome:

$ echo 'mi' >mu
$ ./muring
^C
$ # after ready for half a minute
$ head mu
mi
miu
mii
miuiu
miiu
miiii
miuiuiuiu
miiuiiu
miiiiu
miiiiiiii
$ grep '^mu$' mu
$ # nothing there

This in fact doesn’t resolve the puzzle posed by Hofstadter, in spite of everything,
there might be an extended and extra complicated derivation that takes extra time
to generate. However in both case, one can rule out a easy and brief
derivation of “mu” from “mi”.

Crawl a Website

This additionally works for creating a listing of hyperlinks that begin from a given
internet web page (albeit solely partially and never fully reliably).

The code for that is fairly simple:

#!/usr/bin/env rc

# obtain an internet web page and extract all hyperlinks in it
fn getl {
    whereas(true)
    {
        curl `{learn} |
        grep -o '<a href="http://niplav.website/[^"]*"' |
        sed 's/^<a href="http://;s/"$//' |
        grep '^https?://'
    }
}

tail -f hyperlinks | getl | stdbuf -i0 -oL awk '!a[$0]++' >>hyperlinks

This code needs to be comprehensible: The file hyperlinks comprises the beginning
internet web page to be crawled. That is then curled and all outgoing hyperlinks
are extracted with a sequence of filtering out non-links utilizing grep
and sed. The outcomes are then filtered for outcomes that had been already
obtained, and appended to the hyperlinks file once more–a chic demonstration
of a pipe ring.

$ echo https://en.wikipedia.org/wiki/Main_Page >hyperlinks
$ ./crawler
^C
$ tail hyperlinks
https://en.wikipedia.org/wiki/Main_Page
https://lists.wikimedia.org/mailman/listinfo/daily-article-l
https://wikimediafoundation.org/our-work/wikimedia-projects/
https://commons.wikimedia.org/wiki/
https://www.mediawiki.org/wiki/
https://meta.wikimedia.org/wiki/
https://en.wikibooks.org/wiki/
https://www.wikidata.org/wiki/
https://en.wikinews.org/wiki/
https://en.wikiquote.org/wiki/

Hashes of Hashes

To make use of a extra superfluous and enjoyable instance, one can consider hexadecimal
strings of a sure size as being closed beneath a given hash
perform. For instance, the set of the hexadecimal strings of size 32 is
closed beneath the MD5 hash sum. That
signifies that making use of a hash perform to a component of this set outcomes
within the member of a set.

The likelihood that there exists a hexadecimal string of
size 32 that’s it is personal MD5 hash sum is roughly
$1-frac{1}{e}≈63%$ (see this stackoverflow
question).

This may be illustrated simply with a toy instance: the set of hexadecimal
strings with size 2, and a hash sum that’s merely the primary two
characters of the MD5 sum of the enter (right here referred to as f2md5sum). Then one
can attempt to discover such a hard and fast level with a line of rc:

$ for(i in `{seq 0 255 | awk '{ printf("%.2xn", $0) }'}) { j=` md5sum ; if(~ $i $j) echo $i $j }
6b 6b
$ md5sum
6b
6bf60475e53919fb39d07c0bb66c9c6e  -

Since there are in fact collisions on this easy hash perform, it
may be very possible that for the set H of hexadecimal strings of size 2,
there will probably be some parts h∈H in order that there isn’t a ingredient v∈H so
that f2md5sum(v)=h.

However there are cycles for this set and operation: sequences of strings
h₁,h₂,h₃,…,hₙ in order that f2md5sum(h₁)=h₂, f2md5sum(h₂)=h₃,
…, f2md5sum(hₙ)=h₁. One can discover such cycles by writing a bit
script utilizing a pipe ring:

#!/usr/bin/env rc

fn oipl {
    whereas(learn | eval $*) {}
}

tail -f sums | oipl md5sum | stdbuf -i0 -oL grep -o '^..' >>sums

It offers the specified outcomes:

$ echo 6b >sums
$ ./hashring
$ head sums
6b
6b
6b
6b
6b
6b
6b
6b
6b
6b
$ echo cc >sums
$ ./hashring
$ head -50 sums
cc
87
07
30
d5
16
5b
05
b1
08
43
f0
92
ed
4b
71
72
8f
advert
33
4f
aa
d4
8b
e4
0a
87
07

Within the final instance, one can see such a cycle beginning with 87 and ending
with 0a, in addition to a collision: cc and 0a each have the hash 87.

Theoretically, one might use this methodology to search out cycles for longer
hash sums, and whereas it will be fascinating to discover a string that’s it is
personal SHA1 sum, truly doing it
looks as if a frivolous waste of power and computing energy.

Thankfully for me, anyone else has achieved this already,
making a gif that shows its personal MD5 sum (made by
spq):