Свёртка строк на SectorC (лонгрид)
Вчера я обещал рассказать что я придумал, чтобы компактнее выводить строки в языке SectorC. Напомню, это компактный компилятор подмножества Си, который занимает один сектор (512 байт).
Для начала посмотрим что доступно в компиляторе для вывода текста. В самом языке для этого ничего нет, но если заглянуть в стандартную библиотеку языка, которая подключается автоматически, то можно увидеть там функции print_char(), print_u16() и print_i16(), предназначенные, соответственно, для вывода символа, заданного его кодом, целого числа без знака и целого числа со знаком.
Соответственно вывод «Hello» выглядит так:
print_ch = 72; print_char(); // H
print_ch = 101; print_char(); // e
print_ch = 108; print_char(); // l
print_ch = 108; print_char(); // l
print_ch = 111; print_char(); // o
Очень многословно. Когда я вчера написал «песню о пиве» в таком формате, программа получилась чересчур длинной. Мне захотелось как-то её упросить. Вот как я рассуждал.
Код задаётся целым типом int, который имеет в этом языке 65536 значений. Поскольку мне нужны не все буквы, выглядит так как будто в одно число можно запихнуть несколько знаков. Но сколько?
Для начала посмотрим сколько символов вообще используется. Цифры меня не интересуют (числа выводятся отдельной функцией), поэтому выкинем их:
import sys
from collections import Counter
data = Counter(x for x in ''.join(sys.stdin.readlines()) if x > '9' or x < '0')
print(data)
Вот что получилось:
Counter({' ': 2306, 'e': 1305, 'o': 1108, 't': 903, 'l': 702, 'b': 601, 'n': 600, 'a': 598, 's': 497, 'r': 403, 'f': 300, 'w': 300, '\n': 298, 'd': 298, 'h': 202, ',': 200, '.': 200, 'u': 100, 'T': 99, 'i': 99, 'k': 99, 'p': 99, 'm': 4, 'G': 1, 'N': 1, 'y': 1})
Двадцать шесть символов. Жаль не шестнадцать, было бы удобно хранить — как я говорил выше, значений в целом типе помещается 65536 штук. Какая связь? Чтобы это понять, разберёмся откуда взялось число 65536.
Оно вытекает из особенностей машинного хранения. Минимальная единица хранения — бит, хранит всего два состояния, — биты, в свою очередь, собраны по восемь штук в байты. Тип int в данном случае — это два байта.
Отсюда получается, байт — восемь бит по два значения или 2⁸ = 256 значений, два байта — 256² = 65536. В десятичной системе выглядит довольно бессмысленно, но если перейти на шестнадцатеричную, где цифры записываются от 0…9, A…F, с префиксом 0x (он ставится чтобы различить две формы записи числа), то становится понятнее.
Тогда число 65536 будет выглядеть как 0xFFFF — визуально распадается на два байта по 256 (0xFF) значений или на четыре полубайта по 16 (0xF).
Я решил хранить символы в полубайтах. Поскольку символов у меня 26, а в полубайте помещается 16 значений, то одно значение пришлось занять префиксом — если он встречается, то мы используем вторую таблицу символов. Под префикс я выделил 0xF. Таким образом, в одном int можно закодировать от двух до четырёх символов.
Например, число 0x2F40 или 0x2 0xF 0x4 0x0 означает, что мы смотрим второй символ в первой таблице, потом переключаемся на вторую (так как встретили 0xF) и смотрим там четвёртый символ, а символ 0x0 имеет специальное значение, — он не выводится и нужен для того, чтобы у нас была возможность закодировать строку, которая короче, чем могла бы поместиться.
В первую таблицу я поместил самые часто встречающиеся символы, во вторую — те, что встречаются реже. Получилось намного компактнее. Например, строка «hello» в моём алфавите выводится вот так:
s = 21023; ps(); s = 53; ps(); // 0x521F, 0x35
Поскольку по техническим причинам число проще обрабатывать с конца, то я разворачиваю ту часть строки, которая кодируется. Это легко заметить по тому, что префиксное значение 0xF у меня находится в конце числа 0x521F.
Код для преобразования строк в такую форму выглядит следующим образом:
input = 'hello'
from itertools import *
# основная таблица
t0 = [' ', 'e', 'o', 't', 'l', 'b', 'n', 'a', 's', 'r', 'f', 'w', '\n', 'd']
# и дополнительная
t1 = ['h', ',', '.', 'u', 'T', 'i', 'k', 'p', 'm', 'G', 'N', 'y']
# поиск символов в таблицах
def conv(ch):
try:
yield t0.index(ch) + 1
except ValueError:
yield 0xF
yield t1.index(ch) + 1
# подготовка к разбиению по группам, которые будут кодироваться вместе
def make_shifter():
pos = 0
gr = 0
def shifter(v):
nonlocal pos
nonlocal gr
if pos == 4:
pos = 0
gr += 1
# префикс переключения таблиц не может остаться в одиночестве,
# поэтому мы не можем оставить его в хвосте
if pos == 3 and v == 0xF:
pos = 1
gr += 1
else:
pos += 1
return (v, gr, )
return shifter
shifter = make_shifter()
# нумеруем группы символов
gen = (shifter(x) for x in chain(*(conv(ch) for ch in input)))
# собираем группы символов вместе
gen = groupby(gen, key = lambda x: x[1])
# двигаемся по собранным группам, собираем их в число
for x in gen:
sum = 0
for y in list(x[1])[::-1]:
sum *= 16
sum += y[0]
print("s = {}; ps(); ".format(sum))
Теперь только осталось запрограммировать декодирующую часть в SectorC. У нас будет две функции — одна достаёт из числа по одном полубайту за раз, вторая преобразовывает полубайт в соответствующий символ. Как всё работает в деталях объяснять не буду, покажу с минимальными комментариями.
Первая выглядит совсем просто:
int s; // input
void ps() {
while( s ){
c = s & 15;
c2c();
s = s >> 4;
if( s == ( 0 - 1 ) ){ s = 0; } // signed workaround
}
}
Напоминаю, что вы языке у функции нет аргументов и возможности вернуть значение — всё делается через глобальные переменные, поэтому код выглядит странновато.
Строка с комментарием нужна, так как число у нас знаковое (то есть возможные 65536 значений делятся пополам, часть значений считается отрицательным, другая часть — положительными). У отрицательных чисел есть особенность — битовый сдвиг (>>) хоть и считается эквивалентом деления на два, но из минус единицы ноль не делает.
c2c тут — как раз функция, которая должна преобразовывать код в символ (code-to-character). Она выглядит сложнее. Поскольку массивов в языке тоже нет, приходится выкручиваться как-то иначе. Самый простой способ — инструкциями if проверять каждое значение и найдя нужно, записать в специальную переменную искомый код.
Сначала я так и сделал, но выглядело, опять же, громоздко. В итоге, переделал чуть попроще: код сравнения выделил в короткую функцию x(), а пару что во что превращается закодировал в один int:
int c; // input
int x;
void x() { if( c == ( x >> 8 ) ){ print_ch = x & 255; } }
После такого кодирования функция code-to-character стала выглядеть вот так:
void c2c() {
c = c + shift;
x = 288; x(); x = 613; x(); x = 879; x(); x = 1140; x(); x = 1388; x();
x = 1634; x(); x = 1902; x(); x = 2145; x(); x = 2419; x(); x = 2674; x();
x = 2918; x(); x = 3191; x(); x = 3338; x(); x = 3684; x(); x = 4200; x();
x = 4396; x(); x = 4654; x(); x = 4981; x(); x = 5204; x(); x = 5481; x();
x = 5739; x(); x = 6000; x(); x = 6253; x(); x = 6471; x(); x = 6734; x();
x = 7033; x();
if( c != 15 ){ print_char(); }
shift = 0; if( c == 15 ){ shift = 15; }
}
Как видите, код 0xF (15) устанавливает флаг сдвига значений shift, который в следующий раз складывается с кодом (c + shift) и сдвигает значение на следующем декодировании. Заметно, что нигде нет else, потому что этого оператора в языке тоже нет!
Как будто бы рассказал всё.
Вместо вывода — интересный своей компактностью компилятор, автору моё уважение, — я даже и не подозревал, что в таком малом объёме можно уложить полноценный язык! Очень и очень круто!
Привет. Такая просьба к тебе. У тебя очень классный шаблон «Эгеи», прям то, что надо. Минимализм в сочетании с удобством для чтения.
Возможно ли выложить эту тему для таких товарищей как я? Так как навыки отсутствуют, хочется блог на Эгее, а текущие шаблоны как-то не совем то, что надо.
Пожалуй, надо выложить, да. Бывает, что просят, наверное сегодня-завтра выложу.
Ох, вот за это большое спасибо. И за быстрый ответ, и за такую отзывчивость!
П.С. Сегодня! Сегодня! Сегодня! :)
https://github.com/bolknote/bolk-aegea-theme
Короче, скачал, поставил, почему то она выглядит как Простая/Plane — один в один. То есть ничего не поменялось.
Нет такой ширины в постах, размер шрифтов и отступы и тд. — как на вашем блоге.
Может что то не понимаю или делаю не так? Или что то настроить надо?
Хотя там делать ничего не надо было: установил Эгею, создал папку bolk, распаковал туда вашу тему, клацнул в админке выбор темы и... на выходе никакого праздник, ой Болк-темы, а Плэйн.
В папку user/themes/bolk поставили? Попробуйте ещё кеши скинуть (браузера и Эгеи). Я сейчас попереключал у себя туда-сюда, явно меняется.
Вот собственно после вашего последнего комментария проблема решена.
Евгений, еще раз спасибо за отклик и тему, приятно смотреть и пользоваться! :)
Болкнот снова торт! :)
Не ожидал, что такое интересно кому-то))