Skip to content

Instantly share code, notes, and snippets.

View zwegner's full-sized avatar

Zach Wegner zwegner

  • Austin, TX, USA
View GitHub Profile
@zwegner
zwegner / anti_wordle.py
Last active January 27, 2022 00:53
Prove adversarial wordle has no 3-move solutions
# Proof of optimality of 4-move solution to adversarial Wordle
# https://qntm.org/files/wordle/index.html
import array
import collections
with open('wordle-words.txt') as f:
normal_words = [word.strip() for word in f]
with open('wordle-fake-words.txt') as f:
all_words = [word.strip() for word in f] + normal_words
@zwegner
zwegner / rand_popcnt.c
Created January 10, 2022 23:12
Generate a random number with a given popcount, bisect + PDEP
#include <immintrin.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
// PRNG modified from the public domain RKISS by Bob Jenkins. See:
// http://www.burtleburtle.net/bob/rand/smallprng.html
typedef struct {
@zwegner
zwegner / measure-store-buffer-false-dependencies.py
Last active September 7, 2020 08:36
A tool for measuring the performance of false dependencies in store forwarding
# Test address matching in store forwarding
#
# This tests a mechanism discussed in these references:
#
# * US Patent 2008/0082765 A1
# https://patentimages.storage.googleapis.com/73/b9/bf/b258f3e3985f47/US20080082765A1.pdf
# * Fallout: Leaking Data on Meltdown-resistant CPUs
# https://mdsattacks.com/files/fallout.pdf
# * Stack Overflow: What are the microarchitectural details behind MSBDS (Fallout)?
# https://stackoverflow.com/a/56213609
@zwegner
zwegner / p1_p0156.py
Last active September 2, 2020 01:56
Find uops that execute on p1 pre-ICL and on p0156 on ICL (x86-info-term example query code)
import re
from x86_info_term import get_cache
args, cache = get_cache()
uops_info = cache['datasets']['uops_info']['data']
for inst in uops_info:
for form in uops_info[inst]['forms']:
if 'ICL' in form['arch'] and 'SKX' in form['arch']:
@zwegner
zwegner / flopsort.py
Created July 27, 2020 03:58
Quick+dumb way to sort an array to try and maximize Hamming distance between adjacent elements
import random
def hamming(a, b):
x = a ^ b
c = 0
while x:
x &= x - 1
c += 1
return c
@zwegner
zwegner / wordcount.py
Created July 8, 2020 21:03
Assembly generator script in Python, for making a fast wc -w
import collections
import contextlib
import sys
# Register class, for GPRs and vector registers
_Reg = collections.namedtuple('Reg', 't v')
class Reg(_Reg):
def __str__(self):
names = ['ax', 'cx', 'dx', 'bx', 'sp', 'bp', 'si', 'di']
if self.t == 'r' and self.v < 8:
@zwegner
zwegner / utf8_prob.py
Created June 30, 2020 18:41
Calculate probability of N-byte sequence being part of a valid UTF-8 sequence
from fractions import Fraction
ascii = range(0, 0x80)
cont = range(0x80, 0xC0)
cont_2_0 = range(0xA0, 0xC0)
cont_2_2 = range(0x80, 0xA0)
cont_3_0 = range(0x90, 0xC0)
cont_3_2 = range(0x80, 0x90)
leader2 = range(0xC2, 0xE0)
leader3_0 = range(0xE0, 0xE1)
@zwegner
zwegner / gist:0202c60b9410d029b5cfc5c5643e3374
Last active January 13, 2020 07:07 — forked from dougallj/gist:9211fd24c3759f7f340dede28929c659
Ternary logic multiplication (0, 1, unknown)
import itertools
N_BITS = 8
MASK = (1 << N_BITS) - 1
# Bit class, which stores values as a truth table of up to two variables
class Bit:
def __init__(self, op, bit_a=None, bit_b=None):
self.op = op
# Remove variables when the truth table doesn't depend on them
@zwegner
zwegner / gist:6841688fa897aef64a11016967c36f2d
Created January 13, 2020 02:30
Ternary logic multiplication (0, 1, unknown)
N_BITS = 8
MASK = (1 << N_BITS) - 1
class Ternary:
def __init__(self, ones, unknowns):
self.ones = ones & MASK
self.unknowns = unknowns & MASK
def __add__(self, other):
x = self.ones + other.ones
u = self.unknowns | other.unknowns | (x ^ (x + self.unknowns + other.unknowns))
@zwegner
zwegner / gist:5079097
Last active December 14, 2015 11:28
A simple program that counts the number of monotonic, dependent, and distinct functions of 4 boolean variables. I wrote this for a little mini-contest for my Digital Logic Design class in 2010. There was only one other student who solved it, and his Java code was wayyy longer and uglier. As I thought this was a fairly elegant little program, I'm…
#include <stdio.h>
const int mask[4] = { 0x5555, 0x3333, 0x0F0F, 0x00FF };
int count_table(int *table, char *lbl) {
int count, x;
for (count = x = 0; x < 1<<16; x++)
count += table[x];