Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A log of interesting posts and ideas accumulated over time.

Code Log

A log of resources and ideas ranging in topics from programming language design and Go internals to bit twiddling and optimization.

2019-09-16

CRAPL academic-strength open-source licence

(stub)

Coq proof language

Kimball Germane provides an introduction to the Coq theorem prover.

Coq implements a dependently-typed strongly-normalizing programming language that allows users to express formal specifications of programs. Coq assists the user in finding artifacts that meet a specification and from which it can extract a certified implementation in Haskell, Racket, or OCaml automatically. This talk will iterate through a series of increasingly-precise specifications of a commonly-used function and the experience of a Coq user meeting these specifications.

Defining natural numbers in terms of successor:

Inductive nat : Set :=
  | 0 : nat
  | S : nat -> nat.

Eval compute in 0.
Eval compute in (S 0).
Eval compute in (S (S (S 0))). (* 3 *)

Proving associativity of addition using induction:

Fixpoint add (a b : nat) : nat :=
  match a with
  | 0 => b
  | S n => S (add n b)
  end.

Theorem add_assoc : forall (a b c : nat),
  (add a (add b c)) = (add (add a b) c).
Proof.
intros a b c.
induction a. simpl. reflexivity.
simpl. rewrite -> IHa. reflexivity.
Qed.

Projects using Coq and resources:

(* notable projects
   Vellvm
   Verified Software Toolchain
   Bedrock
   ceL4 and CertiKOS - verified kernels
   CompCert
   Ynot
*)

(* Resources
   Coq Reference Manual
   Coq'Art - Interactive Theorem Proving and Program Development
   Certified Programming with Dependent Types - Alan Chlipala
   Software Foundation
*)

I wanted to talk a little about some cool projects that are being done with Coq. Vellvm is verified LLVM, so that's what it sounds like; Verified Software Toolchain and Ynot are frameworks to reason about C programs and imperative programs; Bedrock reasoning about assembly language; there are some verified kernels that are fully verified; and CompCert is a gigantic project which aimed to have a formalized C compiler and they succeeded.

One of the researchers at the University of Utah, John Regehr - they do hardening for compilers and fuzzying for C compilers and CompCert had the fewest number of bugs and the only bugs it had were in the unverified parts, which was the front-end parser, and since then, that project has verified their front-end parser. So there's good reason to think that there are not mistakes in CompCert.

They [CompCert] define the semantics for C and the semantics for assembly and their high-level proof is that the semantics are preserved across compilation. The chain includes register allocation, so it has stuff about graph coloring - on their website there's a diagram that shows all of the phases that they've proven.

He mentions the Idris programming language as being dependently typed.

Idris is a dependently typed programming language that is getting more popular and I wonder if they would extract to Idris differently where you had to provide a proof.

https://www.youtube.com/watch?v=ngM2N98ppQE

Gemini Guidance Computer

(stub) https://en.m.wikipedia.org/wiki/Gemini_Guidance_Computer

Saturn Launch Vehicle Digital Computer

(stub)

Memory was in the form of 13-bit syllables, each with a 14th parity bit. Instructions were one syllable in size, while data words were two syllables (26 bits).

The LVDC was highly redundant and reliable:

For reliability, the LVDC used triple-redundant logic and a voting system. The computer included three identical logic systems. Each logic system was split into a seven-stage pipeline. At each stage in the pipeline, a voting system would take a majority vote on the results, with the most popular result being passed on to the next stage in all pipelines. This meant that, for each of the seven stages, one module in any one of the three pipelines could fail, and the LVDC would still produce the correct results.

There are 18 simple instructions.

https://en.m.wikipedia.org/wiki/Saturn_Launch_Vehicle_Digital_Computer

Apparently, the LVDC was hand-compiled:

Young (American) programmers just out of college were then employed to manually compile the FORTRAN program into the assembly language of the embedded LVDC CPU, and presumably to make whatever other adjustments are needed when you pass from the computing environment of a large computer to a smaller embedded system.

http://apollo.josefsipek.net/LVDC.html

2019-09-15

Backtracking regexp in Go

Doug Clark wrote a regular expression library for Go that allows backtracking and does not have the constant-time guarantees of the built-in regexp package.

GMP pi computation

GMP can be used to compute pi and is the fastest implementation of those surveyed by Nick Craig-Wood.

curl https://gmplib.org/download/misc/gmp-chudnovsky.c --output gmp-chudnovsky.c
gcc -s -Wall -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm

Ubuntu on Raspberry Pi 4

The Raspberry Pi 4 changed to 64-bit, so most operating systems other than the default Raspbian distribution are not currently compatible. CloudKernels walks through their process of building a 64-bit bootable Ubuntu image for the Pi 4.

https://blog.cloudkernels.net/posts/rpi4-64bit-image/

2019-09-13

C char array and pointer

(stub) https://stackoverflow.com/questions/10186765/what-is-the-difference-between-char-array-and-char-pointer-in-c

Go memory model

(stub) https://golang.org/ref/mem

Profiling Go programs

(stub) https://blog.golang.org/profiling-go-programs

Go as a compiler construction language

If self compilation was an early goal of Go, it would have been more compiler oriented - a design I would greatly appreciate.

Go turned out to be a fine language in which to implement a Go compiler, although that was not its original goal. Not being self-hosting from the beginning allowed Go's design to concentrate on its original use case, which was networked servers. Had we decided Go should compile itself early on, we might have ended up with a language targeted more for compiler construction, which is a worthy goal but not the one we had initially.

https://golang.org/doc/faq#What_compiler_technology_is_used_to_build_the_compilers

Early Go development

The debugger was originally named ogle. Old versions of the FAQ mention that "'Ogle' would be a good name for a Go debugger." https://web.archive.org/web/20110902121904/http://golang.org:80/pkg/exp/ogle/

A vector container package used to exist for sequential storage with specialized versions for int and string. https://web.archive.org/web/20120326025602/http://golang.org:80/pkg/container/vector/

The first commit after the hello world programs contains an early annotated Go spec. https://github.com/golang/go/blob/18c5b488a3b2e218c0e0cf2a7d4820d9da93a554/doc/go_spec

In Rob Pike's Gophercon 2014 talk "Hello, Gophers!", he discusses the language inspiration and development. https://talks.golang.org/2014/hellogophers.slide

TODO: read original spec

Go compiler naming

The Go compiler borrows from the Plan 9 naming scheme:

The 6g (and 8g and 5g) compiler is named in the tradition of the Plan 9 C compilers, described in http://plan9.bell-labs.com/sys/doc/compiler.html (see the table in section 2). 6 is the architecture letter for amd64 (or x86-64, if you prefer), while g stands for Go.

https://web.archive.org/web/20100813130556/http://golang.org/doc/go_faq.html

Plan 9 compilers:

  • 0a, 1a, 2a, 5a, 7a, 8a, ka, qa, va - assemblers
  • 0c, 1c, 2c, 5c, 7c, 8c, kc, qc, vc - C compilers
  • 0l, 1l, 2l, 5l, 7l, 8l, kl, ql, vl - loaders

https://en.wikipedia.org/wiki/List_of_Plan_9_applications

2019-09-12

The Go gopher formerly named Gordon

The well known mascot of Go is called simply "the Go gopher". https://blog.golang.org/gopher

However, in its early days, it was known as "Gordon the Go Gopher". This can be seen on the homepage of Glenda, the Plan 9 Bunny, in the Internet Archive, from about 2009-12-06 to 2013-04-01.

Go SSA tools

(stub)

Annotated bibliography of 106 papers relating to SSA form: http://www.dcs.gla.ac.uk/~jsinger/ssa.html

Plan 9 applications

(stub)

Plan 9 even has a file system filter rot13fs.c to transform traffic with ROT13.

Functional higher-order functions in Go

Using higher-order functions borrowed from functional languages in Go such as apply, filter, and reduce is considered an anti-pattern and for loops are instead preferable.

https://github.com/robpike/filter

Redis persistance using fork

RDB maximizes Redis performances since the only work the Redis parent process needs to do in order to persist is forking a child that will do all the rest. The parent instance will never perform disk I/O or alike.

...

RDB needs to fork() often in order to persist on disk using a child process. Fork() can be time consuming if the dataset is big, and may result in Redis to stop serving clients for some millisecond or even for one second if the dataset is very big and the CPU performance not great. AOF also needs to fork() but you can tune how often you want to rewrite your logs without any trade-off on durability.

...

Whenever Redis needs to dump the dataset to disk, this is what happens:

  • Redis forks. We now have a child and a parent process.
  • The child starts to write the dataset to a temporary RDB file.
  • When the child is done writing the new RDB file, it replaces the old one.

This method allows Redis to benefit from copy-on-write semantics.

...

Log rewriting uses the same copy-on-write trick already in use for snapshotting. This is how it works:

  • Redis forks, so now we have a child and a parent process.
  • The child starts writing the new AOF in a temporary file.
  • The parent accumulates all the new changes in an in-memory buffer (but at the same time it writes the new changes in the old append-only file, so if the rewriting fails, we are safe).
  • When the child is done rewriting the file, the parent gets a signal, and appends the in-memory buffer at the end of the file generated by the child.
  • Profit! Now Redis atomically renames the old file into the new one, and starts appending new data into the new file.

https://redis.io/topics/persistence

Forking in threaded applications

(stub)

2019-09-10

Binary combinatory logic esoteric lang

Binary combinatory logic is a formulation of combinatory logic using only the symbols 0 and 1.

<term> ::= 00 | 01 | 1 <term> <term>
  • 00 represents the K operator.
  • 01 represents the S operator.
  • 1 <term> <term> represents the application operator (<term1> <term2>).

https://esolangs.org/wiki/Binary_combinatory_logic

GrammaTech CodeSonar and CodeSurfer

(stub) https://www.grammatech.com/products/codesonar

2019-09-09

Local development certificate generation

(stub) https://github.com/FiloSottile/mkcert

GitHub public keys vulnerable

GitHub public keys are available for anyone to access at the URL https://github.com/username.keys. Unless configured otherwise, ssh sends all public keys until one works. By storing all GitHub keys, a server can identify the client by their key.

2019-09-08

macOS Catalina default shell is zsh

Starting in macOS Catalina, the default shell will be zsh. The version of bash used by macOS is stuck on 3.2 because newer versions newer versions are licensed under GPL v3.

Scripting OS X gives an in depth walkthrough on migrating to zsh: https://scriptingosx.com/2019/06/moving-to-zsh/

2019-09-06

Stack-based language compilation

"Compilation of Stack-Based Languages (Abschlußbericht)" by M. Anton Ertl and Christian Pirker (1998) describes techniques for compiling stack-based languages.

RAFTS is a framework for applying state of the art compiler technology to the compilation of stack-based languages like Forth and Postscript. The special needs of stack-based languages are an efficient stack representation, fast procedure calls, and fast compilation. RAFTS addresses the stack representation problem by allocating stack items to registers such that most stack accesses in the source program are register accesses in the machine language program, and by eliminating most stack pointer updates. To achieve fast calls, RAFTS performs these optimizations interprocedurally and also performs procedure inlining and tail call optimization. Fast compilation is achieved by selecting fast algorithms and implementing them efficiently.

...

The basic block code generation reduces the number of stack pointer updates to at most one per stack and basic block. It is possible to reduce the number much more. E.g., in procedures where all stack items are allocated to registers, no stack pointer update is needed at all. Like register allocation, stack pointer update minimization has to be performed interprocedurally to achieve a significant effect.

2019-09-05

Chrome offline dinosaur source

The source for the offline dinosaur game in Chrome is available in Chromium and written in JavaScript. https://github.com/chromium/chromium/blob/master/components/neterror/resources/offline.js

Project idea: extract the dinosaur game into a standalone page.

The T-Rex appears to be named "Stan the Offline Dino" as referenced in several test files:

<head><title>Welcome to Stan the Offline Dino's Homepage</title></head>

https://github.com/chromium/chromium/blob/master/chromecast/browser/test/data/dynamic_title.html

Wikipedia documents the evolution of the dinosaur game:

If the user tries to browse when offline, a message is shown that they are not connected to the Internet. An illustration of the "Lonely T-Rex" dinosaur is shown at the top, designed by Sebastien Gabriel. From September 2014, tapping the dinosaur (in Android or iOS) or pressing space or ↑ (on desktop) launches a browser game called "T-Rex Runner" in which the player controls a running dinosaur by tapping the screen (in Android or iOS) or pressing space, ↑ or ↓ (on desktop) to avoid obstacles, including cacti and, from June 2015, pterodactyls. In 2016, another feature was added to the game. When the player reaches 700 points the game begins to switch between day (white background, black lines and shapes) and night (black background, white lines and shapes). During September 2018, for Google Chrome's 10th birthday, a birthday cake causing the dinosaur to wear a birthday hat when collected was added. Reaching a score of 900 will switch the colour scheme back to day, and the switch back and forth will occur at further subsequent milestones. The game is also available at the chrome://network-error/-106 and chrome://dino pages. The game's code is available on the Chromium site.

https://en.wikipedia.org/wiki/List_of_Google_Easter_eggs#Chrome

Conway's game of life

(stub)

Query language research

BYU computer science professor Kimball Germane, specializes in programming languages and his current research is in utilizing the SQLite VM byte code to construct DSL query languages that are more expressive than allowed through SQL.

2019-09-04

Google Easter eggs

Wikipedia lists many Easter eggs hidden in Google search. Included is a selection of those queries:

  • "<blink>", "blink tag", or "blink html" includes samples of the blink element in the results.
  • "conway's game of life" on a desktop browser generates a running configuration of the game to the right of the search results. The process can also be stopped and altered by the user.
  • "google in 1998" on a desktop browser will generate a layout similar to the one Google used for its search engine in 1998.
  • "is google down" returns with "No".
  • "kerning" will add spaces between the letters of the word "kerning" in the search results.
  • "keming" will remove spaces between the letters of the word "keming".
  • "<marquee>", "marquee tag", or "marquee html" will apply the marquee element to the results count at the top of the results.
  • "minesweeper" will have a playable game of minesweeper. Users can select between three modes: easy, medium and hard.
  • "pac-man", "google pacman" or "play pacman" will show the Pac-Man related interactive Google Doodle from 2010. Clicking Insert Coin twice will enable a second player, Ms. Pac-Man.
  • "pluto" describes Pluto as "Our favorite dwarf planet since 2006" in the Knowledge Graph.
  • "recursion" includes a "Did you mean: recursion" link back to the same page.
  • "text adventure" or "google easter eggs" using most popular modern browsers (except Safari) and opening the browser's developer console will trigger a text-based adventure game playable within the console.
  • "tic tac toe" will show a playable game of tic-tac-toe. Users can select to play against the browser at different levels - "easy", "medium" or "hard" (called "impossible") - or against a friend. An alternative way to find the game is to search "shall we play a game".

https://en.wikipedia.org/wiki/List_of_Google_Easter_eggs

2019-09-03

C main signatures

A common extension to C supported by Unix systems adds a third parameter for environment information.

int main(void)
int main(int argc, char *argv[])
int main(int argc, char *argv[], char *envp[])

Alternatively, the environment is available in <unistd.h> with extern char **environ;.

In C, a function without parameters accepts any number of arguments, so int main() accepts any arguments, whereas int main(void) accepts none. C++ treats those two forms identically.

https://stackoverflow.com/questions/2108192/what-are-the-valid-signatures-for-cs-main-function

2019-08-29

Aheui - esoteric language in Hangul

Aheui is the first esolang designed for Hangul, the Korean writing system.

The language specification provides an introduction into Korean orthography and lists the function of each vowel and consonant. https://aheui.readthedocs.io/en/latest/specs.en.html

Interpreters are implemented in a dozen languages, including Go and self interpreted in Aheui:

AVIS is a cell based editor for Aheui: https://github.com/aheui/avis

Aheui in a polyglot: https://codegolf.stackexchange.com/questions/31506/99-bottles-of-beer-99-languages/#31539

2019-08-28

μ6 esoteric language

μ6 is a low-level esolang based on μ-recursive functions.

https://github.com/bforte/mu6

Google Chrome history database

Google Chrome history is stored locally as a SQLite3 database and can be easily exported.

cd ~/Library/Application\ Support/Google/Chrome/Default/
sqlite3 History

sqlite> .headers on
sqlite> .mode csv
sqlite> .output my-chrome-output.csv

sqlite> SELECT DATETIME(last_visit_time/1000000-11644473600, 'unixepoch', 'localtime'), url
        FROM urls
        ORDER BY last_visit_time DESC;

https://yuji.wordpress.com/2014/03/10/export-chrome-history-as-csv-spreadsheet/

2019-08-26

X11 for macOS

The XQuartz open source project is a version of the X11 windowing system for macOS.

https://www.xquartz.org

APOD Automator script

Automator in macOS can be used to automatically download the current NASA Astronomy Picture of the Day and set it as the desktop background.

https://macosxautomation.com/automator/apod/index.html

Go sync.Map

Map is like a Go map[interface{}]interface{} but is safe for concurrent use by multiple goroutines without additional locking or coordination. Loads, stores, and deletes run in amortized constant-time.

The Map type is specialized. Most code should use a plain Go map instead, with separate locking or coordination, for better type safety and to make it easier to maintain other invariants along with the map content.

The Map type is optimized for two common use cases:

  1. when the entry for a given key is only ever written once but read many times, as in caches that only grow, or
  2. when multiple goroutines read, write, and overwrite entries for disjoint sets of keys. In these two cases, use of a Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

https://golang.org/pkg/sync/#Map

Go sync.Once

Once is an object that will perform exactly one action.

Do calls the function f if and only if Do is being called for the first time for this instance of Once. In other words, given var once Once, if once.Do(f) is called multiple times, only the first call will invoke f, even if f has a different value in each invocation. A new instance of Once is required for each function to execute.

https://golang.org/pkg/sync/#Once

Used by crypto/elliptic: https://golang.org/src/crypto/elliptic/elliptic.go

Go types package

Package go/types declares the data types and implements the algorithms for type-checking of Go packages.

https://godoc.org/go/types

Alan Donovan provides a detailed tutorial on the use of the package: https://github.com/golang/example/tree/master/gotypes

Info has maps to store the relationship between identifiers and objects. Only non-nil maps in Info are populated, letting API clients control the information needed from the type checker. The field Defs records declaring identifiers and Uses records referring identifiers.

type Info struct {
  Defs       map[*ast.Ident]Object
  Uses       map[*ast.Ident]Object
  Implicits  map[ast.Node]Object
  Selections map[*ast.SelectorExpr]*Selection
  Scopes     map[ast.Node]*Scope
  ...
}

TODO: Continue reading at https://github.com/golang/example/tree/master/gotypes#function-and-method-types

Referring page: https://stackoverflow.com/questions/40266003/how-to-assert-ast-typespec-to-int-type-in-golang

gosec - Go security checker

Gosec inspects source code for security problems by scanning the Go AST.

https://github.com/securego/gosec

Floating point math associativity

GCC optimizes pow(a, 2) into a*a, but does not optimize pow(a, 6) or a*a*a*a*a*a into (a*a*a)*(a*a*a) because floating point math is not associative, though associativity and other optimizations can be enabled with compiler flags.

https://stackoverflow.com/questions/6430448/why-doesnt-gcc-optimize-aaaaaa-to-aaaaaa

C++ compiler division by zero optimization

The C++ compiler does not throw a division by zero exception when d == 0.

int d = 0;
d /= d;

C++ does not have a "Division by Zero" Exception to catch. The behavior you're observing is the result of Compiler optimizations:

  1. The compiler assumes Undefined Behavior doesn't happen
  2. Division by Zero in C++ is undefined behavior
  3. Therefore, code which can cause a Division by Zero is presumed to not do so.
    • And, code which must cause a Division by Zero is presumed to never happen
  4. Therefore, the compiler deduces that because Undefined Behavior doesn't happen, then the conditions for Undefined Behavior in this code (d == 0) must not happen
  5. Therefore, d / d must always equal 1.

https://stackoverflow.com/questions/57628986/why-doesnt-d-d-throw-a-division-by-zero-exception-when-d-0

2019-08-25

Go language proverbs

Rob Pike philosophizes at Gopherfest SV 2015 and provides the following proverbs for teaching or understanding Go:

  • Don't communicate by sharing memory, share memory by communicating.
  • Concurrency is not parallelism.
  • Channels orchestrate; mutexes serialize.
  • The bigger the interface, the weaker the abstraction.
  • Make the zero value useful.
  • interface{} says nothing.
  • Gofmt's style is no one's favorite, yet gofmt is everyone's favorite.
  • A little copying is better than a little dependency.
  • Syscall must always be guarded with build tags.
  • Cgo must always be guarded with build tags.
  • Cgo is not Go.
  • With the unsafe package there are no guarantees.
  • Clear is better than clever.
  • Reflection is never clear.
  • Errors are values.
  • Don't just check errors, handle them gracefully.
  • Design the architecture, name the components, document the details.
  • Documentation is for users.
  • Don't panic.

https://www.youtube.com/watch?v=PAAkCSZUG1c https://go-proverbs.github.io

XKCD surveys

(stub)

2019-08-24

Yorick experimentation

Matrices in Yorick are column-major, so to transpose a column vector to a row vector, we increase the dimensionality of the matrix using a "-" pseudo-index.

> u=[1,2,3,4]
> u
[1,2,3,4]
> u(-,)
[[1],[2],[3],[4]]

Outer product of column vectors uv = uvᵀ:

> u=[1,2,3,4]
> v=[1,10,100]
> v(-,)
[[1],[10],[100]]
> u*v(-,)
[[1,2,3,4],[10,20,30,40],[100,200,300,400]]
> transpose(u*v(-,))
[[1,10,100],[2,20,200],[3,30,300],[4,40,400]]

Inner product (dot product), defined as ⟨u, v⟩ = uv, is represented in Yorick using the "+" sign. The plus sign selects "the dimension to be iterated over in the summation of the inner product."

> u=[1,2,3]
> v=[4,5,6]
> u(+)*v(+)
32

Matrix multiplication is composed of dot products at each position and is thus represented using the plus sign. The transpose matches "normal" matrix multiplication since Yorick is column-major.

> a=[[1,2],[3,4]]
> b=[[5,6],[7,8]]
> a(+,)*b(,+)
[[19,43],[22,50]]
> transpose(a(+,)*b(,+))
[[19,22],[43,50]]

The original NumPy authors were familiar with Yorick and borrowed the concept of broadcasting from Yorick. https://stackoverflow.com/questions/26948776/where-did-the-term-broadcasting-come-from/26950256#26950256

JEH-Tech explains Yorick with fantastic diagrams. https://web.archive.org/web/20170102091157/http://www.jeh-tech.com/yorick.html

2019-08-23

Go terminal package

Package crypto/ssh/terminal provides support functions for dealing with terminals, as commonly found on UNIX systems.

https://godoc.org/golang.org/x/crypto/ssh/terminal

Yorick syntax and building

Yorick has optional semicolons to enable easier to type statements into the terminal. When omitted, the lexer must insert semicolons so that the parser works correctly which complicates the grammar significantly. This context sensitivity is called a "lexical tie-in" and is discouraged.

Yorick can be built from source from its repository. https://github.com/dhmunro/yorick

Simple hello world:

> print, "Hello, World!"
"Hello, World!"

Go astutil package

Package astutil contains common utilities for working with the Go AST. https://godoc.org/golang.org/x/tools/go/ast/astutil

2019-08-22

Split a subdirectory into a separate repo

A subdirectory can be split into a separate repo, the inverse of a repo merge. Any history existing outside of that subdirectory will not appear in the split repo. This causes problems if that folder has been moved.

git filter-branch --prune-empty --subdirectory-filter FOLDER-NAME BRANCH-NAME

https://help.github.com/en/articles/splitting-a-subfolder-out-into-a-new-repository

2019-08-21

VSCode TextMate grammar performance

(stub)

2019-08-20

Go Native Client support

Russ Cox describes in detail the process of implementing support for Native Client (NaCl) in Go 1.3 and the architecture restrictions that added complexity.

Go 1.13 is the last release that will run on NaCl. https://tip.golang.org/doc/go1.13

Comparing binaries and source code

(stub)

Control flow graph function matching

Joxean Koret proposes a heuristic based on the idea that "different basic blocks and edges are different interesting pieces of information". The Koret-Karamitas algorithm "КОКА" gets features at function, basic block, edge, and instruction level, assigns a different prime value to each different feature, and then generates a hash of the product.

Huku classifies basic blocks in 7 categories: normal, entry points, exit points, traps, self-loops, loop heads and loop tails. In the same way, he classifies 4 different kinds of edges: basis, forward, back edges and cross-links.

Huku uses instruction histograms to classify instructions in 4 categories based on their functionality: arithmetic, logic, data transfer, and redirection.

JCry - a ransomware written in Go

JCry is downloaded as a fake update to Adobe Flash Player through a compromised website. It drops encryption and decryption programs into Startup, then encrypts the 1MB of all files with significant extensions. It then demands payment for a decryption key through an onion link in a Tor browser.

Raspberry Pi arcade

Recently while in San Francisco, I stumbled upon a Raiden II arcade machine in Musée Mécanique. As a child, one of my favorite games was Raiden X, a Flash spinoff of the Raiden series, so it was fun to play the original game.

Project idea: create a dedicated arcade machine using a Raspberry Pi, monitor, joystick, and buttons to play arcade games like the Raiden series, Pac Man, or Dig Dug or Flash games like Raiden X. Software like MAME (Multiple Arcade Machine Emulator) exists for arcade games, so those would be simple, but the Flash format poses issues because support has been largely dropped because the runtime has security issues and the PC controls would need to be mapped to a joystick and buttons.

Origins of the Raspberry Pi

The Raspberry Pi was developed to introduce more people to programming and at a low cost. The cost of $35 was a goal early on and drove many design decisions. Later once produced in bulk, upgrades could be made while staying within the price range. https://www.techrepublic.com/article/inside-the-raspberry-pi-the-story-of-the-35-computer-that-changed-the-world/

Transposing an 8x8 bit matrix

"Hacker's Delight", Chapter 7-3

This procedure treats the 8×8-bit matrix as 16 2×2-bit matrices and transposes each of the 16 2×2-bit matrices. The matrix is then treated as four 2×2 sub-matrices whose elements are 2×2-bit matrices and each of the four 2×2 sub-matrices are transposed. Finally, the matrix is treated as a 2×2 matrix whose elements are 4×4-bit matrices and the 2×2 matrix is transposed.

unsigned long long x;
x = x & 0xAA55AA55AA55AA55LL |
  (x & 0x00AA00AA00AA00AALL) << 7 |
  (x >> 7) & 0x00AA00AA00AA00AALL;
x = x & 0xCCCC3333CCCC3333LL |
  (x & 0x0000CCCC0000CCCCLL) << 14 |
  (x >> 14) & 0x0000CCCC0000CCCCLL;
x = x & 0xF0F0F0F00F0F0F0FLL |
  (x & 0x00000000F0F0F0F0LL) << 28 |
  (x >> 28) & 0x00000000F0F0F0F0LL;

2019-08-18

Geohash in Go assembly

(stub) https://mmcloughlin.com/posts/geohash-assembly

Find nth set bit

(stub)

2019-08-13

Efficient integer square root algorithm

(stub)

2019-08-10

Constant-time bits

Go version 1.13 guarantees execution time of Add, Sub, Mul, RotateLeft, and ReverseBytes in package math/bits to be independent of the inputs.

CL 170758:

// Variable time
func Add64(x, y, carry uint64) (sum, carryOut uint64) {
  yc := y + carry
  sum = x + yc
  if sum < x || yc < y {
    carryOut = 1
  }
  return
}
// Constant time
func Add64(x, y, carry uint64) (sum, carryOut uint64) {
  sum = x + y + carry
  carryOut = ((x & y) | ((x | y) &^ sum)) >> 63
  return
}

https://golang.org/cl/170758

Go crypto/subtle

Package subtle implements functions that are often useful in cryptographic code but require careful thought to use correctly such as constant-time comparisons or copies.

func ConstantTimeByteEq(x, y uint8) int
func ConstantTimeCompare(x, y []byte) int
func ConstantTimeCopy(v int, x, y []byte)
func ConstantTimeEq(x, y int32) int
func ConstantTimeLessOrEq(x, y int) int
func ConstantTimeSelect(v, x, y int) int

https://golang.org/pkg/crypto/subtle/

2019-08-08

Go regression testing

Nearly every fixed bug or issue has an associated test created in the test/fixedbugs directory to prevent regressions. Each test is tagged with a comment on the first line indicating the mode of testing: run, compile, errorcheck, or build. If a test has an associated directory, it becomes rundir, compiledir, etc. The level of automation and thorough nature of these tests is impressive.

https://github.com/golang/go/tree/master/test/fixedbugs

Go objdump

objdump disassembles executable files in Go's Plan 9 assembly syntax.

https://golang.org/cmd/objdump/

2019-08-06

Go context concurrency pattern

(stub) https://blog.golang.org/context

Communicating sequential processes

(stub) https://www.youtube.com/watch?v=hB05UFqOtFA

Less is exponentially more

(stub) https://commandcenter.blogspot.com/2012/06/less-is-exponentially-more.html

Retrospective on early Go development

(stub) https://commandcenter.blogspot.com/2017/09/go-ten-years-and-climbing.html

Go interface implementation

(stub) https://research.swtch.com/interfaces

Go design philosophy

(stub)

"Go at Google: Language Design in the Service of Software Engineering"

Go grammar is mostly regular:

Compared to other languages in the C family, its grammar is modest in size, with only 25 keywords (C99 has 37; C++11 has 84; the numbers continue to grow). More important, the grammar is regular and therefore easy to parse (mostly; there are a couple of quirks we might have fixed but didn't discover early enough). Unlike C and Java and especially C++, Go can be parsed without type information or a symbol table; there is no type-specific context.

https://talks.golang.org/2012/splash.article

TODO: Expand on CSP and arena allocator.

2019-08-05

Go 1.13

Selected features to be added in Go 1.13:

  • More number literal prefixes are supported.
  • The restriction that a shift count must be unsigned is removed.
  • math/bits: The execution time of Add, Sub, Mul, RotateLeft, and ReverseBytes is now guaranteed to be independent of the inputs.

https://tip.golang.org/doc/go1.13

2019-08-03

Semantics of unary plus and minus

(stub) https://groups.google.com/forum/#!topic/golang-nuts/aOIn6y_pX_U

Go proposal for 128 bit integers

(stub)

Go runtime errors

Runtime errors are distinguished by the no-op function RuntimeError() in the runtime.Error interface.

Google Go team and monorepos

(stub)

2019-08-02

Go experimental subpackages

utf8string provides an efficient way to index strings by rune rather than by byte. https://godoc.org/golang.org/x/exp/utf8string

apidiff determines whether two versions of the same package are compatible. https://godoc.org/golang.org/x/exp/apidiff sumdb/gosumcheck checks a go.sum file against a go.sum database server. https://godoc.org/golang.org/x/exp/sumdb/gosumcheck

shiny/materialdesign provides named colors and icons specified by Material Design. https://godoc.org/golang.org/x/exp/shiny/materialdesign/colornames https://godoc.org/golang.org/x/exp/shiny/materialdesign/icons

shiny/screen and shiny/driver provide interfaces and drivers for accessing a screen. https://godoc.org/golang.org/x/exp/shiny/screen https://godoc.org/golang.org/x/exp/shiny/driver

Red-black trees in functional languages

Chris Okasaki demonstrated that red-black trees can be efficiently and elegantly implemented in functional languages. He simplifies insert to have four unbalanced cases and one balanced case. http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps

Red-black trees have become one of the most common persistent data structures in functional languages. https://en.wikipedia.org/wiki/Red–black_tree

Go reusable containers

  • container/ring provides a circular linked list.
  • container/heap provides a heap interface and functions to operate on the heap.
  • container/list provides a doubly linked list.

2019-08 (undated)

Git repository merging

(stub)

2019-07-31

Go hex dump

Dumper in encoding/hex writes a hex dump in the format of hexdump -C. https://golang.org/pkg/encoding/hex/#Dumper

2019-07-30

Go test helpers

t.Helper() can be called to mark the caller as a test helper function and skips printing file and line information for that function.

encoding/asci85 has a clever Errorf and comparison wrapper:

testEqual(t, "Encode(%q) = %q, want %q", p.decoded, strip85(string(buf)), strip85(p.encoded))

func testEqual(t *testing.T, msg string, args ...interface{}) bool {
  t.Helper()
  if args[len(args)-2] != args[len(args)-1] {
    t.Errorf(msg, args...)
    return false
  }
  return true
}

Go binary.Varint

Unsigned integers are serialized 7 bytes at a time, starting with the least significant bits. The most significant bit indicates if there is a continuation byte. https://golang.org/src/encoding/binary/varint.go

Go bounds check elimination

Issue #14808 provides a list of bound check eliminations used or not used by Go compiler including the following:

var a[]int
…
use a[0], a[1], a[2] // three bound checks
// can be improved as
_ = a[3]             // early bounds check
use a[0], a[1], a[3] // no bound checks
// or
a = a[:3:len(a)]     // early bound check
use a[0], a[1], a[3] // no bound checks
// or
use a[3], a[2], a[1] // one bound check

https://github.com/golang/go/issues/14808

Bounds check hints in the wild in binary.LittleEndian and binary.BigEndian:

func (littleEndian) Uint16(b []byte) uint16 {
  _ = b[1] // bounds check hint to compiler; see golang.org/issue/14808
  return uint16(b[0]) | uint16(b[1])<<8
}
func (littleEndian) PutUint16(b []byte, v uint16) {
  _ = b[1] // early bounds check to guarantee safety of writes below
  b[0] = byte(v)
  b[1] = byte(v >> 8)
}

Grid processing algorithms

Matrices using image processing algorithms to group coordinates in grid: https://stackoverflow.com/questions/24985127/efficiently-grouping-a-list-of-coordinates-points-by-location-in-python

A max-heap can be used to order rectangles in grid by size: https://stackoverflow.com/questions/5810649/finding-rectangles-in-a-2d-block-grid

2019-07-23

Go json.RawMessage

RawMessage is a raw encoded JSON value implementing Marshaler and Unmarshaler used to delay decoding or precompute an encoding.

In the wild:

type clientResponse struct {
  Id     uint64           `json:"id"`
  Result *json.RawMessage `json:"result"`
  Error  interface{}      `json:"error"`
}

https://golang.org/src/net/rpc/jsonrpc/client.go

Example from json docs:

// use a precomputed JSON during marshal
h := json.RawMessage(`{"precomputed": true}`)
c := struct {
  Header *json.RawMessage `json:"header"`
  Body   string           `json:"body"`
}{Header: &h, Body: "Hello Gophers!"}
// delay parsing part of a JSON message
type Color struct {
  Space string
  Point json.RawMessage // delay parsing until we know the color space
}
type RGB struct {
  R, G, B uint8
}
var c Color
err := json.Unmarshal(`{"Space": "RGB", "Point": {"R": 98, "G": 218, "B": 255}}`, &c)
var dst interface{}
switch c.Space {
  case "RGB":
  dst = new(RGB)
}
err = json.Unmarshal(c.Point, dst)

https://golang.org/pkg/encoding/json/#RawMessage

2019-07-20

QLOCKTWO text-based clock

While visiting Zürich, Switzerland, I saw a store selling text-based clocks made by QLOCK2. The clocks have a grid of letters that light up to spell out the time.

For example, in 5:28 would be rounded to 5:30 and displayed in German as "ES IST HALB FÜNF".

E S K I S T A F Ü N F
Z E H N Z W A N Z I G
D R E I V I E R T E L
V O R F U N K N A C H
H A L B A E L F Ü N F
E I N S X A M Z W E I
D R E I P M J V I E R
S E C H S N L A C H T
S I E B E N Z W Ö L F
Z E H N E U N K U H R

In English, it would be "IT IS HALF PAST FIVE".

I T L I S A S A M P M
A C Q U A R T E R D C
T W E N T Y F I V E X
H A L F S T E N F T O
P A S T E R U N I N E
O N E S I X T H R E E
F O U R F I V E T W O
E I G H T E L E V E N
S E V E N T W E L V E
T E N S E O'C L O C K

Project idea: develop a web browser extension to replace the new tab page with a more aesthetically pleasing page including a QLOCKTWO-style clock and artistic backgrounds. The search bar is redundant with the address bar and need not be included. Depending on the level of minimalism desired, feeds of the user's favorite websites could be displayed.

2019-07-19

Apollo mission streams

(stub)

2019-07-17

Fast addition and subtraction

(stub) https://www.chosenplaintext.ca/articles/radix-2-51-trick.html

Constant-time cryptography

When writing constant-time code, timing should not depend on secret information.

Secret information may only be used in an input to an instruction if that input has no impact on what resources will be used and for how long. ... Today’s languages and compilers weren’t really built for this, so it's a challenge. ... The compiler might decide that your code would be faster if it used variable-time instructions. There are even cases where an optimizing compiler will see that you are trying to, say, avoid using an if statement, and the compiler puts the if statement back in because it knows it will be faster.

https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html

Code can be verified to be constant-time using a patch to Valgrind made by Adam Langley: https://github.com/agl/ctgrind

BigInt in ES2020

  • BigInt is a numeric primitive for arbitrary precision integers introduced in ES2020: https://v8.dev/features/bigint
  • BigInt has its own type and can be defined with a n suffix (typeof 42n === 'bigint').
  • A BigInt is not strictly equal to a Number (===), but is abstractly equal (==).
  • When coerced to a boolean, BigInt follows the same logic as Number.
  • Binary +, -, *, and ** all work. / and % work, rounding towards zero.
  • Bitwise operations |, &, <<, >>, and ^ assume a two's complement representation for negative values.
  • Unary - negates, though unary + is not supported because asm.js expects +x to produce either a Number or an exception.
  • Unsigned right shift >>> is unsupported because BigInt is always signed.
  • BigInt64Array and BigUint64Array, make it easier to efficiently represent lists of 64-bit signed and unsigned integers.

Detecting signals in Go

src-d/go-git intercepts signals to exit cleanly from Git calls using os/signal and context.

c := make(chan os.Signal, 1)
signal.Notify(c, os.Interrupt)

https://github.com/src-d/go-git/blob/master/_examples/context/main.go

2019-07-16

go-intervals

Library for performing set operations on 1-dimensional intervals, such as time ranges: https://github.com/google/go-intervals

pprof

Tabletop Whale

2019-07-15

Uber Go libraries

2019-07-14

LLVM IR in Go

2019-07-13

GNU Multiple Precision Arithmetic Library

2019-07-12

Bit twiddling reference

(stub) http://graphics.stanford.edu/~seander/bithacks.html

2019-07-06

Interstellar film script differences

IMSDb has a draft script from March 12, 2008 for Interstellar that drastically different from the final film version. In it, Murph is a boy and the Chinese passed through the wormhole long before NASA and figured out how to manipulate gravity. https://www.imsdb.com/scripts/Interstellar.html

Project idea: make a tool to format film scripts to be more pleasant to read. Scripts on IMSDb are consistently formatted, albeit with some inaccuracies, so could be mapped to another format.

2019-07-04

Send channels and receive channels in Go

There are three types of channels: bidirectional chan, receive-only <-chan, and send-only chan<-. A bidirectional channel can be casted to either receive-only or send-only, but cannot be converted back.

https://stackoverflow.com/questions/13596186/whats-the-point-of-one-way-channels-in-go

First seen in the Go syntax definitions in GitHub's Semantic project: https://github.com/github/semantic/blob/master/src/Language/Go/Syntax.hs

2019-07-03

Elm

Elm is a pure functional UI design DSL with strong static type checking and "no runtime exceptions in practice".

XMLisp - Lisp with XML syntax

Project idea: implement a Lisp-like language with implicit returns, higher order functions, and expressions as values. This would be a more capable successor to XMLang that would introduce type safety and would parse with encoding/xml rather than JSX.

https://github.com/andrewarchi/xmlang

<func name="fib" params="n int">
  <if>
    <eq>n 0</eq>
    0
    <if>
      <eq>n 1</eq>
      1
      <add>
        <fib><sub>n 1</sub></fib>
        <fib><sub>n 2</sub></fib>
      </add>
    </if>
  </if>
</func>
<fib>5</fib>

Go crypto/rand

crypto/rand operates on *big.Int, unlike math/rand.

rand.Reader is a global, shared instance of a cryptographically secure random number generator that reads from OS-specific APIs.

2019-06-27

Ahead-of-time and just-in-time compilation

2019-06-26

μ-recursive function

(stub)

https://en.wikipedia.org/wiki/μ-recursive_function

Whitespace is supposedly based on μ-recursive functions: https://cs.stackexchange.com/questions/95790/do-any-programming-languages-use-general-recursive-functions-as-their-basis

HaPyLi programming language

HaPyLi is a programming language designed to compile to Whitespace, with syntax derived from Haskell, Python, and Lisp. HaPyLi uses the Whitespace heap to store strings and globals. It supports inline Whitespace, but requires that all arguments and local variables be popped and exactly one value be pushed. The standard library includes alloc, similar to malloc in C, but there is no corresponding free implementation.

import "stdlib/base.hpl"

def power(x y) =
    (if (== y 1)
        x
        (* x (power x (- y 1))))

def main() = (print-number (power 2 10))

Unfortunately, as the homepage is defunct, the compiler source is no longer available.

Marinus Oosters created a 99 bottles of beer program written in HaPyLi: http://www.99-bottles-of-beer.net/language-hapyli-2556.html

While developing HaPyLi, the author posted a question on Haskell monads during code generation: https://stackoverflow.com/questions/607830/use-of-haskell-state-monad-a-code-smell

2019-06-25

Go math/bits proposal

All bit twiddling functions, except popcnt, are already implemented by runtime/internal/sys and receive special support from the compiler in order to "to help get the very best performance". However, the compiler support is limited to the runtime package and other Golang users have to reimplement the slower variant of these functions.

Go 1.13 signed shift counts

In Go 1.13, shift counts (<< and >>) are no longer required to be unsigned and when negative, a panic occurs.

This requires an estimated minimum of two extra instructions per non-constant shift: a test and a branch to be check at run-time, as done for make. The compiler can omit the check for unsigned and constant values and when it is able to prove that the operand is non-negative.

As a last resort, an explicit uint conversion or mask in the source code will allow programmers to force the removal of the check, just as an explicit mask of the shift count today avoids the oversize shiftcheck.

2019-06-19

Assembly performing slower than high level programs

Go blank identifier uses

Disable unused declaration error:

_ = unused

To import a package solely for its side-effects (initialization), use the blank identifier as explicit package name:

import _ "lib/math"

https://golang.org/ref/spec#Import_declarations

Static type assertion:

type T struct{}
var _ I = T{}       // Verify that T implements I.
var _ I = (*T)(nil) // Verify that *T implements I.

https://golang.org/doc/faq#guarantee_satisfies_interface

Interspersing delimiters without branching

The Go Programming Language: gopl.io/ch1/echo1

var s, sep string
for i := 1; i < len(os.Args); i++ {
  s += sep + os.Args[i]
  sep = " "
}
fmt.Println(s)

Semantic source code library by GitHub

Yorick programming language

"Yorick is an interpreted programming language for scientific simulations or calculations, postprocessing or steering large simulation codes, interactive scientific graphics, and reading, writing, or translating large files of numbers." http://dhmunro.github.io/yorick-doc/

"Arrays are first-class objects that can be operated on with a single operation. Since the virtual machine understands arrays, it can apply optimized compiled subroutines to array operations, eliminating the speed penalty of the interpreter." https://www.linuxjournal.com/article/2184

"Yorick is good at manipulating elements in N-dimensional arrays conveniently with its powerful syntax." https://en.wikipedia.org/wiki/Yorick_(programming_language)

I was referred to Yorick by Matt Borthwick as it is his favorite programming language for physics. A trick to compute the product of the elements of an array and avoid overflows is to take the exponentiation of the sum of the natural logs of the elements: exp(sum(ln(arr))). https://github.com/matt6deg

2019-06-18

Go unnamed method receiver

A method can have a receiver without a name.

func (CmdReceivePack) Usage() string

https://github.com/src-d/go-git/blob/master/cli/go-git/receive_pack.go

2019-06-13

Go embedded struct fields

Embedded struct fields have no name and promote fields and methods to another struct. https://golang.org/ref/spec#Struct_types

Discovered in encoding/json/encode.go:

type jsonError struct{ error }
type A struct {
  foo int
}
type B struct {
  A
  bar int
}
b := B{A{10}, 3}
// b.bar, b.foo, b.A are accessible

https://golangtutorials.blogspot.com/2011/06/anonymous-fields-in-structs-like-object.html

2019-06-11

Git branch cleanup tool

Project idea: after a PR has been merged and the branch deleted on the remote, any local clones of this branch remain and should be deleted.

Process:

  • Scan repo(s) for all branches
  • Exclude dev, master, currently checked out branch, and branches with an open PR
  • Delete all merged branches

2019-06-09

Go sync.Pool

2019-06-06

Password crossword

The 2013 Adobe breach has the credentials of millions of users and the passwords are encrypted insecurely using Triple DES.

In an XKCD comic, Randall Munroe creates a crossword puzzle of solving the password blocks using the given password hints. https://www.xkcd.com/1286/)

Using statistics of the most common passwords, one could provide a word bank common passwords that could be used while solving such a crossword puzzle.

Go reflection to view and set unexported fields

Reflection is designed to allow any field to be accessed, but outside of the definition package, only exported fields can be modified (The Go Programming Language, Donovan and Kernighan).

However, using unsafe.Pointer and (*reflect.Value).UnsafeAddr, unexported values can be assigned to, though doing so potentially interferes with garbage collection. https://stackoverflow.com/questions/17981651/in-go-is-there-any-way-to-access-private-fields-of-a-struct-from-another-packag

Deleting value in Go map

An element can be deleted from a map using delete(m, key) similar to delete m[key] in Javascript.

Go modules synchronizer

When working in a project using modules, each package and sub-package requires specific dependency versions which protects a package from breaking changes in its dependencies, but it makes changing code in multiple packages simultaneously difficult.

Project idea: a tool that watches locally changed packages and updates interdependencies would greatly simplify this process.

2019-06-05

Go runtime package

Operations to interact with runtime system and low-level reflect type information. https://golang.org/pkg/runtime/

Discovered from attempt to print line numbers in error messages. https://stackoverflow.com/questions/24809287/how-do-you-get-a-golang-program-to-print-the-line-number-of-the-error-it-just-ca

2019-06-04

Text normalization

  • Text normalization in Go: https://blog.golang.org/normalization
  • Detailing on NFC, NFD, NFKC, and NFKD methods of transforming text: https://unicode.org/reports/tr15/
  • Normalizing to NFC compacts text, giving substantial savings to languages like Korean
    • Project idea: Make a keyboard with Hangul input that converts to NFC as you type, but allows for deletion by character rather than by block
  • Allows for normalization of look-alikes

2019-06-03

Goto in Python

In Python, an April Fools joke added goto, label, and comefrom. http://entrian.com/goto/

Discovered from a comparison of throw to comefrom in favor of Go's error handling decisions. https://news.ycombinator.com/item?id=19778097

Git annotations for ls

There are answers here, but they don't appear to be efficient: https://unix.stackexchange.com/questions/249363/git-bash-ls-show-git-repo-folders

Note the branch annotations at the end:

drwxr-xr-x 1 0018121 Domain Users    0 Dec 14 14:33 MyProject/ (develop)
drwxr-xr-x 1 0018121 Domain Users    0 Dec 14 14:17 Data/
drwxr-xr-x 1 0018121 Domain Users    0 Dec 14 12:08 MyApp/ (master)
-rw-r--r-- 1 0018121 Domain Users 399K Aug  4 10:41 readme.txt

Git checkout shortcut

  1. Scan for git directories: https://stackoverflow.com/questions/11981716/how-to-quickly-find-all-git-repos-under-a-directory
  2. List all branches for each repo and create aliases for each

2019-05-31

Assembly in Go

Guide to the assembly used in Go: https://golang.org/doc/asm

The assembler's parser treats period and slash as punctuation, so the assembler allows the middle dot character U+00B7 and the division slash U+2215 in identifiers and rewrites them to plain period and slash. For example, fmt.Printf and math/rand.Int are rewritten to fmt·Printf and math∕rand·Int.

2019-05-27

RE2

(stub) https://github.com/google/re2

2019-05-26

Code Search

Google Code Search performs regular expression matching with a trigram index. https://github.com/google/codesearch

https://swtch.com/~rsc/regexp/regexp4.html

Binary RegExp

(stub)

https://github.com/rsc/binaryregexp

Continuation-passing style

Functions in CPS take an extra argument, the continuation, a function of one argument. The result is returned by calling the continuation function with this value.

Procedure returns are calls to a continuation, intermediate values are all given names, argument evaluation order is made explicit, and tail calls call a procedure with the same continuation.

Functional and logic compilers often use CPS as an intermediate representation, whereas imperative or procedural compilers would use static single assignment form (SSA).

; Direct style
(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

; Continuation-passing style
(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))

https://en.wikipedia.org/wiki/Continuation-passing_style

Go math/bits package

Arithmetic functions: add/sub with carry and mul/div with remainder. Bit manipulation: leading/trailing zeros count, bit count, one count, reverse, and rotate.

https://golang.org/pkg/math/bits/

2019-05-24

Git autocomplete

Git autocompletion can be installed by downloading the following file and sourcing in profile.

curl https://raw.githubusercontent.com/git/git/master/contrib/completion/git-completion.bash -o ~/.git-completion.bash

https://apple.stackexchange.com/questions/55875/git-auto-complete-for-branches-at-the-command-line

2019-05-21

Approxidate

Git integration with Go

go-git is a highly extensible git implementation library written in pure Go.

2019-05-20

Datalog Disassembly

(stub) https://github.com/GrammaTech/ddisasm

2019-05-13

Static single assignment form

In compiler design, SSA is a property of an intermediate representation, which requires that each variable is assigned exactly once, and every variable is defined before it is used.

Variables in the are split into versions so that every definition gets its own version.

y := 1
y := 2
x := y

Rewritten in SSA:

y1 := 1
y2 := 2
x1 := y2

https://en.wikipedia.org/wiki/Static_single_assignment_form

Go loop bound reevaluation

Loop bound expressions can be optimized in some cases to be evaluated once: https://stackoverflow.com/questions/41327984/does-go-runtime-evaluate-the-for-loop-condition-every-iteration

Go 1.7 switched to using SSA for the compiler which generates more compact, more efficient code and provides a better platform for optimizations such as bounds check elimination.

2019-05-09

Unicode property trie lookup

(stub) https://github.com/foliojs/unicode-properties

2019-05 (undated)

W3C CSS Color Module Level 4 changes

(stub)

EDI Parsing

(stub)

2019-05-06

Powerline

Powerline formats the shell prompt and vim status line into great looking segments. It uses patched fonts like FiraCode to render custom Unicode glyphs. Powerline Gitstatus is a segment for showing the status of a Git working copy.

2019-03-29

Unlambda, AsciiDots, and Ook esoteric languages

Unlambda is a minimal functional language based on combinatory logic. It is the first functional Turing tarpit: https://esolangs.org/wiki/Unlambda

AsciiDots executes using dots travelling along ascii art paths taking inspiration from electrical engineering: https://esolangs.org/wiki/AsciiDots

Ook! is a simple mapping of Brainf*** instructions to trinary combinations of Ook., Ook?, and Ook!: https://esolangs.org/wiki/Ook!

2019-03-28

TrumpScript

2019-03-19

Customizing Windows command prompt

(stub)

2019-02-26

GHIDRA - NSA reverse engineering and decompilation tool

(stub)

2018-12 (undated)

Trie data structure

(stub)

2018-09-25

Countering Trusting Trust

Originally written as email on 2019-09-25 to Dr. Peter Aldous following up with conversation from 2019-09-24:

I did some more research into Reflections on Trusting Trust by Thompson and came across this dissertation "Fully Countering Trusting Trust through Diverse Double-Compiling" by David A. Wheeler that counters such an attack.

Essentially, he proves that a questionable compiler can be verified by comparing a trusted compiler, compiled from source, then compiled by itself with the result of a questionable compiler executable compiling that first trusted compiler's source twice. https://www.dwheeler.com/trusting-trust/

Below is a summary of his approach and a link to a more complete summary. Wheeler's site explains some details that the summary glosses over, but the dissertation itself if 199 pages long, so I haven't read that.

Suppose we have two completely independent compilers: A and T. More specifically, we have source code SA of compiler A, and executable code EA and ET. We want to determine if the binary of compiler A - EA - contains this trusting trust attack.

Here's Wheeler's trick:

  • Step 1: Compile SA with EA, yielding new executable X.
  • Step 2: Compile SA with ET, yielding new executable Y.

Since X and Y were generated by two different compilers, they should have different binary code but be functionally equivalent. So far, so good.

Now:

  • Step 3: Compile SA with X, yielding new executable V.
  • Step 4: Compile SA with Y, yielding new executable W.

Since X and Y are functionally equivalent, V and W should be bit-for-bit equivalent. https://www.schneier.com/blog/archives/2006/01/countering_trus.html

As linked from Wheeler's paper, University of Michigan researchers discovered and implemented a hardware backdoor that can be installed by a single employee at the processor's fabrication facility and triggered by a sequence of obscure commands that charge a capacitor, then eventually trigger and grant OS access. This is a scary prospect because of how monumentally difficult it would be to detect such a backdoor. https://www.wired.com/2016/06/demonically-clever-backdoor-hides-inside-computer-chip/

This xkcd comic introduced me to Reflections on Trusting Trust: https://xkcd.com/1755/. The reference can be found in the hover text. In the explain xkcd wiki, Wheeler's paper is mentioned: https://explainxkcd.com/wiki/index.php/1755:_Old_Days.

Reflections on Trusting Trust

Originally written as email on 2019-09-25 to Dad and David

I recently ran across the influential paper "Reflections on Trusting Trust" by Ken Thompson. He describes a vulnerability in which the C compiler source can be modified to install a backdoor into the Unix login command. This compiler source is then compiled into an executable and distributed. If the bugged compiler compiles Unix, will recognize and install this backdoor. It is also bugged so that when it compiles itself, it plants the backdoor thus perpetuating the vulnerability into future versions of the compiler. This exploit is extremely hard to detect because it only exists in the executable, so it won't be seen when looking at the source. In effect, we can't trust any software we did not write ourselves, including compilers.

Here's a link to the paper. It's very short and highly understandable: https://www.archive.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf

I hope you find this interesting and stimulating. I've included an email that I sent to my CS 236 professor following up on a discussion we had yesterday. The conversation started with him describing how I could parse German sentences (which he happens to know) with material from class and morphed into security practices and concerns. This paper has nothing to do with CS 236, but I figure I'll be having many more conversations with him.

2018-07-06

Webkit color implementation

(stub)

2018-06-09

JSX usage outside of React

JSX can be used outside of React as Robert Prehn outlines in his article.

You could use this to do anything that lends itself to functional composition. Some ideas:

  • You could create DSLs with an XML-like syntax within your JavaScript.
  • You could abuse the JSX transform to compile XML configuration or seed data into JavaScript objects (please don't).
  • You could even make a whole XML-syntax functional programming language that compiles to JS (just stop).
<and>
  <or>
    <not>
      {true}
    </not>
    {true}
  </or>
  {true}
  <or>
    {false}
    {true}
  </or>
  {false}
</and>

https://revelry.co/using-jsx-with-other-frameworks-than-react/

See https://github.com/andrewarchi/xmlang

2018-04-25

Using C preprocessor language agnostically

The C preprocessor is independent of the C language and thus can be used with languages that do not have compile-time evaluation.

-E  Stop after the preprocessing stage; do not run the compiler
    proper. The output is in the form of preprocessed source code,
    which is sent to the standard output.

-P  Inhibit generation of linemarkers in the output from the
    preprocessor. This might be useful when running the preprocessor
    on something that is not C code, and will be sent to a program
    which might be confused by the linemarkers.

The source file must be named with a .c suffix and the output can be redirected to a file.

gcc -E -P hello.js.c > hello.js
#define HOWDY

function hello(name) {
  console.log('Hello, ' + name);
#ifdef HOWDY
  console.log('Howdy, ' + name + '!');
#endif
}

2018-03-23

Apollo Guidance Computer source

(stub)

2018-01-30

Implementing arbitrary precision integers

Project idea: arbitrary precision integers could be stored using contiguous integers with carry and borrow used to implement addition and subtraction across boundaries. Multiplication and division would be more difficult.

This idea was sparked by something in a CS 224 Computer Systems lecture.

2017-10-29

youtube-dl video downloader

youtube-dl is a highly configurable command-line program written in Python to download videos from YouTube.com and other video sites.

https://github.com/ytdl-org/youtube-dl

2017-08-28 (latest)

Pi series

The sum of inverse squares is pi squared over six:

\frac{\pi^2}{6} = \sum_{n=1}^{\infty} \frac{1}{n^2}

The arctangent power series of 1 is equal pi/4:

\arctan(x) = 1 - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + ...
\arctan(1) = \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + ...

2017-06-22

Initial Go commits

The first four commits in the Go repository reference the evolution of C, a callback to when Rob Pike worked with Brian Kernighan in the 1980s at Bell Labs. https://stackoverflow.com/questions/21979690/whats-the-story-behind-the-revision-history-of-go/21981037#21981037

convert to Draft-Proposed ANSI C, Brian Kernighan committed on Apr 1, 1988

#include <stdio.h>

main()
{
    printf("hello, world\n");
}

https://github.com/golang/go/commit/0744ac969119db8a0ad3253951d375eb77cfce9e

convert to C, Brian Kernighan committed on Jan 19, 1974

main() {
    printf("hello, world");
}

https://github.com/golang/go/commit/0bb0b61d6a85b2a1a33dcbc418089656f2754d32

hello, world, Brian Kernighan committed on Jul 18, 1972

main( ) {
    extrn a, b, c;
    putchar(a); putchar(b); putchar(c); putchar('!*n');
}
a 'hell';
b 'o, w';
c 'orld';

https://github.com/golang/go/commit/7d7c6a97f815e9279d08cfaea7d5efb5e90695a8

Navigating history on GitHub to earliest commit: https://stackoverflow.com/questions/28533602/how-do-i-navigate-to-the-earliest-commit-in-a-github-repository

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.