Сжать

SQUOZE (сокращенно SQZ ) — это эффективное по памяти представление комбинированного исходного и перемещаемого объектного программного файла с таблицей символов на перфокартах , которое было представлено в 1958 году вместе с ассемблером SCAT. ^{[ 1 ]}^{[ 2 ]} об операционной системе SHARE (SOS) для IBM 709 . ^{[ 3 ]}^{[ 4 ]} Программа такого формата называлась SQUOZE- дека . ^{[ 5 ]}^{[ 6 ]}^{[ 7 ]} Он также использовался на более поздних машинах, включая IBM 7090 и 7094 .

СКВОЗНАЯ колода

Колода SQUOZE содержит закодированную двоичную форму исходного кода языка ассемблера; Колоды SQUOZE преобразуются в абсолютный машинный код и сохраняются в памяти программой-загрузчиком. ^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}

Кодировка символов имени идентификатора

В кодировке SQUOZE идентификаторы в таблице символов были представлены в 50-символьном алфавите , что позволяло 36-битному машинному слову представлять шесть буквенно-цифровых символов плюс два бита флага, тем самым экономя два бита на шесть символов. ^{[ 6 ]}^{[ 1 ]} потому что шесть битов, обычно выделяемых для каждого символа, могут хранить до 64 состояний, а не только 50 состояний, необходимых для представления 50 букв алфавита, и 50 ⁶ < 2 ³⁴.

Сжать коды символов ^{[ 1 ]}
Большинство значительный цифры			Младшие значащие цифры
		декабрь	+0	+1	+2	+3	+4	+5	+6	+7
		октябрь	0	1	2	3	4	5	6	7
декабрь	октябрь	Бин	000	001	010	011	100	101	110	111
+0	0	000	космос	0	1	2	3	4	5	6
+8	1	001	7	8	9	А	Б	С	Д	И
+16	2	010	Ф	Г	ЧАС	я	Дж	К	л	М
+24	3	011	Н	ТО	П	вопрос	Р	С	Т	В
+32	4	100	V	В	Х	И	С	= #	/ %	) ⌑
+40	5	101	+ &	-	- @	+ &	-	*	/	$
+48	6	110	,	.	—	—	—	—	—	—

Использование базы 50 уже сохраняет один бит на каждые три символа, поэтому он использовался в двух трехсимвольных фрагментах. Руководство ^{[ 1 ]} имеет формулу кодирования шести символов ABCDEF: $(A*50^{2}+B*50+C)*2^{17}+(D*50^{2}+E*50+F)$

Например, «SQUOZE», обычно 36 бит: 35 33 37 31 44 17_{(база 8)} будет закодирована двумя 17-битными частями, чтобы уместиться в 34 бита, как ( 0o220231 << 17 ) | 0o175473 == 0o110114575473.

Более простым примером той же логики может быть то, как трехзначное число BCD будет занимать 12 бит, например 987: 9 8 7_{(база 16)} 1001 1000 0111_{(основание 2)} , но любое такое значение можно сохранить непосредственно в 10 битах, сэкономив два бита, например 987: 3db_{(база 16)} 11 1101 1011_{(база 2)} .

Этимология

«Squoze» — шутливое причастие прошедшего времени от глагола «сжимать». ^{[ 5 ]}^{[ 6 ]}

Название SQUOZE позже было заимствовано для аналогичных схем кодирования символов, используемых на DEC ; машинах ^{[ 4 ]} они имели 40-значный алфавит (50 в восьмеричном формате ) и назывались DEC RADIX 50 и MOD40 , ^{[ 11 ]} но иногда его называют DEC Squoze .

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ДОЛЯ 709 Системный комитет, изд. (июнь 1961 г.) [1959]. «Раздел 02: Язык SCAT; Приложение 1: Таблица допустимых символов; Приложение 3: Формат колоды SQUOZE — Глава 8: Словарь». Справочное руководство SOS — Система SHARE для IBM 709 (PDF) . Нью-Йорк, США: SOS Group, Международная корпорация Business Machines . стр. 02.00.01 – 02.00.11, 12.03.08.01 – 12.03.08.02, 12.01.00.01. Х28-1213. Раздача № 1–5. Архивировано (PDF) из оригинала 18 июня 2020 г. Проверено 18 июня 2020 г. С. 12.03.08.01 – 12.03.08.02: […] Используемые позиции битов […] Бит 0 […] Бит 1 […] Биты 2–35 […] по основанию 50 Представление символа с символом заголовка. […] Представление символа по основанию 50 получается следующим образом: […] a. Если символ содержит менее пяти символов, он имеет заголовок (пробел, если он находится в незаголовке). […] б. Символ с заголовком it[s] выравнивается по левому краю, а все неиспользуемые младшие позиции заполняются пробелами. […] в. Каждый символ в символе заменяется его эквивалентом по основанию 50. […] д. Затем результат преобразуется следующим образом: если после того, как каждый символ заменяется его эквивалентом по основанию 50, это ABCDEF, его представление по основанию 50 будет (A*50 ²+Б*50+С)*2 ¹⁷+(Д*50 ²+Е*50+Ф). […] [1] [2]
^ Саломон, Дэвид (февраль 1993 г.) [1992]. Написано в Университете штата Калифорния, Нортридж, Калифорния, США. Чиверс, Ян Д. (ред.). Сборщики и грузчики (PDF) . Серия Эллиса Хорвуда «Компьютеры и их приложения» (1-е изд.). Чичестер, Западный Суссекс, Великобритания: Ellis Horwood Limited / Simon & Schuster International Group . ISBN 0-13-052564-2 . Архивировано (PDF) из оригинала 23 марта 2020 г. Проверено 1 октября 2008 г. (xiv+294+4 страницы)
^ Джейкоб, Брюс; Нг, Спенсер В.; Ван, Дэвид Т.; Родригес, Сэмюэл (2008). «Часть I, глава 3.1.3. Оптимизация локальности в режиме онлайн: динамическое сжатие инструкций и данных» . Системы памяти: кэш, DRAM, диск . Серия Моргана Кауфмана по компьютерной архитектуре и дизайну. Издательство Морган Кауфманн / Elsevier. п. 147. ИСБН 978-0-12-379751-3 . (900 страниц)
^ Перейти обратно: ^а ^б Джонс, Дуглас В. (2018). «Лекция 7, Объектные коды, загрузчики и компоновщики — последние шаги на пути к машинному коду» . Операционные системы, весна 2018 г. Часть коллекции операционных систем CS:3620. Университет Айовы , факультет компьютерных наук. Архивировано из оригинала 6 июня 2020 г. Проверено 6 июня 2020 г.
^ Перейти обратно: ^а ^б Бём, Элейн М.; Стил-младший, Томас Б. (июнь 1958 г.). Машинная реализация символьного программирования - Краткое изложение доклада, который будет представлен на заседании ACM летом 1958 года . ACM '58: Препринты докладов, представленных на 13-м национальном собрании Ассоциации вычислительной техники. стр. 17-1–17-3. дои : 10.1145/610937.610953 . Архивировано из оригинала 6 июня 2020 г. Проверено 6 июня 2020 г. (3 страницы)
^ Перейти обратно: ^а ^б ^с Бём, Элейн М.; Стил-младший, Томас Б. (апрель 1959 г.). «Система SHARE 709: машинная реализация символьного программирования» . Журнал АКМ . 6 (2): 134–140. дои : 10.1145/320964.320968 . S2CID 16545134 . С. 137–138: […] Есть интересная особенность, связанная с кодировкой символов для включения в словарь. В обычном способе выражения символы могут быть составлены из набора из 50 символов. Если бы кодирование было посимвольным, для представления каждого такого символа потребовалось бы шесть бит. Поскольку символ может содержать до шести символов, для представления каждого символа потребуется в общей сложности 36 бит. Это может показаться удобным, поскольку длина слова 709 составляет ровно 36 бит, но небольшое рассмотрение показывает, что это неудачно, поскольку было бы желательно иметь один или два бита в том же слове, что и представление символа, что дает подсказку. к природе символа. Эти флаговые биты могут быть получены. Пусть каждый возможный символ представляет цифру в системе счисления, имеющую база пятьдесят . Теперь шесть символов можно читать как натуральные числа в пятидесятичной системе. Если эти числа преобразовать в обычную систему счисления с основанием два, то для максимального числа потребуется всего 34 бита и будет получен прирост в два бита флага. Это имеет побочную особенность, заключающуюся в уменьшении необходимого количества бит для представления всего кода, но время преобразования значительно перевесило бы экономию, если бы не особая длина слова 709. Вот яркая иллюстрация критического влияния точных характеристик рассматриваемой машины на детали схемы кодирования. […] (7 страниц)
^ Шелл, Дональд Л. (апрель 1959 г.) [октябрь 1958 г.]. «Система SHARE 709: совместные усилия» . Журнал АКМ . 6 (2): 123–127. дои : 10.1145/320964.320966 . S2CID 16476514 . (5 страниц)
^ «Общая информация о системе обработки данных IBM 7090» (PDF) . ИБМ. 1959. стр. 12–13. G22-6505-.
^ Эрман, Джон Роберт; Снайдер, Джеймс Н. (15 апреля 1964 г.). «3.3.2.1 СКАТ». Исполнительная система PORTHOS для IBM 7094 — Руководство пользователя (PDF) . Университет Иллинойса , Лаборатория цифровых компьютеров Высшего колледжа. Архивировано (PDF) из оригинала 07 июня 2020 г. Проверено 7 июня 2020 г. […] SCAT — это ассемблер, состоящий из двух частей, который вкратце работает следующим образом: программы, написанные символически как один порядок на карту, на первом этапе принимаются «компилятором», который сканирует программу на наличие символов и выводит сжатую колоду карт (SQUOZE колода), содержащая таблицы этих символов, а также программу, сжатую и эффективно закодированную. На втором этапе эта колода SQUOZE принимается программой «модификации и загрузки», которая преобразует объектную программу в двоичный машинный язык, который по выбору может быть либо загружен готовым к запуску, либо выведен на абсолютные двоичные карты (23 порядка на карту) для загрузки. и запускается позже. «Листер» может создать печатную версию программы на любом из этих этапов. Символические исправления программы могут быть вставлены во второй этап вместе с колодой SQUOZE. […]
^ Справочное руководство SOS (PDF) . ИБМ . Ноябрь 1959 года.
^ «8.10 .RAD50». Ассемблер PAL-11R - Руководство программиста - Язык ассемблера программ и перемещаемый ассемблер для дисковой операционной системы (2-е исправленное печатное издание). Мейнард, Массачусетс, США: Digital Equipment Corporation . Май 1971 г. [февраль 1971 г.]. п. 8-8. DEC-11-ASDB-D . Проверено 18 июня 2020 г. п. 8-8: […] Системные программы PDP-11 часто обрабатывают символы в специально закодированной форме, называемой RADIX 50 (эту форму иногда называют MOD40 ). Эта форма позволяет упаковать 3 символа в 16 бит […] [3]

Дальнейшее чтение

Уильямс, Эл (22 ноября 2016 г.). «Сжать ваши данные» . Хакадей . Архивировано из оригинала 6 июня 2020 г. Проверено 6 июня 2020 г.

[IBM_1961_SOS-1] Перейти обратно: ^а ^б ^с ^д ДОЛЯ 709 Системный комитет, изд. (июнь 1961 г.) [1959]. «Раздел 02: Язык SCAT; Приложение 1: Таблица допустимых символов; Приложение 3: Формат колоды SQUOZE — Глава 8: Словарь». Справочное руководство SOS — Система SHARE для IBM 709 (PDF) . Нью-Йорк, США: SOS Group, Международная корпорация Business Machines . стр. 02.00.01 – 02.00.11, 12.03.08.01 – 12.03.08.02, 12.01.00.01. Х28-1213. Раздача № 1–5. Архивировано (PDF) из оригинала 18 июня 2020 г. Проверено 18 июня 2020 г. С. 12.03.08.01 – 12.03.08.02: […] Используемые позиции битов […] Бит 0 […] Бит 1 […] Биты 2–35 […] по основанию 50 Представление символа с символом заголовка. […] Представление символа по основанию 50 получается следующим образом: […] a. Если символ содержит менее пяти символов, он имеет заголовок (пробел, если он находится в незаголовке). […] б. Символ с заголовком it[s] выравнивается по левому краю, а все неиспользуемые младшие позиции заполняются пробелами. […] в. Каждый символ в символе заменяется его эквивалентом по основанию 50. […] д. Затем результат преобразуется следующим образом: если после того, как каждый символ заменяется его эквивалентом по основанию 50, это ABCDEF, его представление по основанию 50 будет (A*50 ²+Б*50+С)*2 ¹⁷+(Д*50 ²+Е*50+Ф). […] [1] [2]

[Salomon_1993-2] Саломон, Дэвид (февраль 1993 г.) [1992]. Написано в Университете штата Калифорния, Нортридж, Калифорния, США. Чиверс, Ян Д. (ред.). Сборщики и грузчики (PDF) . Серия Эллиса Хорвуда «Компьютеры и их приложения» (1-е изд.). Чичестер, Западный Суссекс, Великобритания: Ellis Horwood Limited / Simon & Schuster International Group . ISBN 0-13-052564-2 . Архивировано (PDF) из оригинала 23 марта 2020 г. Проверено 1 октября 2008 г. (xiv+294+4 страницы)

[Jacob_2008-3] Джейкоб, Брюс; Нг, Спенсер В.; Ван, Дэвид Т.; Родригес, Сэмюэл (2008). «Часть I, глава 3.1.3. Оптимизация локальности в режиме онлайн: динамическое сжатие инструкций и данных» . Системы памяти: кэш, DRAM, диск . Серия Моргана Кауфмана по компьютерной архитектуре и дизайну. Издательство Морган Кауфманн / Elsevier. п. 147. ИСБН 978-0-12-379751-3 . (900 страниц)

[Jones_2018-4] Перейти обратно: ^а ^б Джонс, Дуглас В. (2018). «Лекция 7, Объектные коды, загрузчики и компоновщики — последние шаги на пути к машинному коду» . Операционные системы, весна 2018 г. Часть коллекции операционных систем CS:3620. Университет Айовы , факультет компьютерных наук. Архивировано из оригинала 6 июня 2020 г. Проверено 6 июня 2020 г.

[Boehm-Steel_1958-5] Перейти обратно: ^а ^б Бём, Элейн М.; Стил-младший, Томас Б. (июнь 1958 г.). Машинная реализация символьного программирования - Краткое изложение доклада, который будет представлен на заседании ACM летом 1958 года . ACM '58: Препринты докладов, представленных на 13-м национальном собрании Ассоциации вычислительной техники. стр. 17-1–17-3. дои : 10.1145/610937.610953 . Архивировано из оригинала 6 июня 2020 г. Проверено 6 июня 2020 г. (3 страницы)

[Boehm-Steel_1959-6] Перейти обратно: ^а ^б ^с Бём, Элейн М.; Стил-младший, Томас Б. (апрель 1959 г.). «Система SHARE 709: машинная реализация символьного программирования» . Журнал АКМ . 6 (2): 134–140. дои : 10.1145/320964.320968 . S2CID 16545134 . С. 137–138: […] Есть интересная особенность, связанная с кодировкой символов для включения в словарь. В обычном способе выражения символы могут быть составлены из набора из 50 символов. Если бы кодирование было посимвольным, для представления каждого такого символа потребовалось бы шесть бит. Поскольку символ может содержать до шести символов, для представления каждого символа потребуется в общей сложности 36 бит. Это может показаться удобным, поскольку длина слова 709 составляет ровно 36 бит, но небольшое рассмотрение показывает, что это неудачно, поскольку было бы желательно иметь один или два бита в том же слове, что и представление символа, что дает подсказку. к природе символа. Эти флаговые биты могут быть получены. Пусть каждый возможный символ представляет цифру в системе счисления, имеющую база пятьдесят . Теперь шесть символов можно читать как натуральные числа в пятидесятичной системе. Если эти числа преобразовать в обычную систему счисления с основанием два, то для максимального числа потребуется всего 34 бита и будет получен прирост в два бита флага. Это имеет побочную особенность, заключающуюся в уменьшении необходимого количества бит для представления всего кода, но время преобразования значительно перевесило бы экономию, если бы не особая длина слова 709. Вот яркая иллюстрация критического влияния точных характеристик рассматриваемой машины на детали схемы кодирования. […] (7 страниц)

[Shell_1959-7] Шелл, Дональд Л. (апрель 1959 г.) [октябрь 1958 г.]. «Система SHARE 709: совместные усилия» . Журнал АКМ . 6 (2): 123–127. дои : 10.1145/320964.320966 . S2CID 16476514 . (5 страниц)

[7090genInfo_1959-8] «Общая информация о системе обработки данных IBM 7090» (PDF) . ИБМ. 1959. стр. 12–13. G22-6505-.

[PORTHOS_1964-9] Эрман, Джон Роберт; Снайдер, Джеймс Н. (15 апреля 1964 г.). «3.3.2.1 СКАТ». Исполнительная система PORTHOS для IBM 7094 — Руководство пользователя (PDF) . Университет Иллинойса , Лаборатория цифровых компьютеров Высшего колледжа. Архивировано (PDF) из оригинала 07 июня 2020 г. Проверено 7 июня 2020 г. […] SCAT — это ассемблер, состоящий из двух частей, который вкратце работает следующим образом: программы, написанные символически как один порядок на карту, на первом этапе принимаются «компилятором», который сканирует программу на наличие символов и выводит сжатую колоду карт (SQUOZE колода), содержащая таблицы этих символов, а также программу, сжатую и эффективно закодированную. На втором этапе эта колода SQUOZE принимается программой «модификации и загрузки», которая преобразует объектную программу в двоичный машинный язык, который по выбору может быть либо загружен готовым к запуску, либо выведен на абсолютные двоичные карты (23 порядка на карту) для загрузки. и запускается позже. «Листер» может создать печатную версию программы на любом из этих этапов. Символические исправления программы могут быть вставлены во второй этап вместе с колодой SQUOZE. […]

[SOS_Reference_1961-10] Справочное руководство SOS (PDF) . ИБМ . Ноябрь 1959 года.

[DEC_1971_PAL-11R-11] «8.10 .RAD50». Ассемблер PAL-11R - Руководство программиста - Язык ассемблера программ и перемещаемый ассемблер для дисковой операционной системы (2-е исправленное печатное издание). Мейнард, Массачусетс, США: Digital Equipment Corporation . Май 1971 г. [февраль 1971 г.]. п. 8-8. DEC-11-ASDB-D . Проверено 18 июня 2020 г. п. 8-8: […] Системные программы PDP-11 часто обрабатывают символы в специально закодированной форме, называемой RADIX 50 (эту форму иногда называют MOD40 ). Эта форма позволяет упаковать 3 символа в 16 бит […] [3]

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]