stringtranslate.com

СЖАТИЕ

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

палуба SQUOZE

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

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

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

Использование базы 50 уже экономит один бит на каждые три символа, поэтому она использовалась в двух трехсимвольных кусках. В руководстве [1] есть формула для кодирования шести символов ABCDEF:

Например, «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» — шутливое причастие прошедшего времени глагола «to squeeze». [5] [6]

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

Смотрите также

Ссылки

  1. ^ abcd SHARE 709 System Committee, ed. (июнь 1961 г.) [1959]. "Раздел 02: Язык SCAT; Приложение 1: Таблица допустимых символов; Приложение 3: Формат колоды SQUOZE - Глава 8: Словарь". Справочное руководство SOS - Система SHARE для IBM 709 (PDF) . Нью-Йорк, США: SOS Group, International Business Machines Corporation . стр. 02.00.01 – 02.00.11, 12.03.08.01 – 12.03.08.02, 12.01.00.01. X28-1213. Распространение № 1–5. Архивировано (PDF) из оригинала 2020-06-18 . Получено 2020-06-18 . стр. 12.03.08.01 – 12.03.08.02: […] Используемые позиции бит […] Бит 0 […] Бит 1 […] Биты 2–35 […] Представление символа с заголовком в системе счисления 50. […] Представление символа с заголовком в системе счисления 50 получается следующим образом: […] а. Если символ имеет менее пяти символов, он озаглавлен (пробелом, если он находится в области без заголовка). […] б. Символ с его заголовком выравнивается по левому краю, а все неиспользуемые позиции младшего разряда заполняются пробелами. […] в. Каждый символ в символе заменяется его эквивалентом в системе счисления 50. […] г. Затем результат преобразуется следующим образом: если символ после замены каждого символа его эквивалентом в системе счисления с основанием 50 равен ABCDEF, то его представление в системе счисления с основанием 50 равно (A*50 2 +B*50+C)*2 17 +(D*50 2 +E*50+F). […][1][2]
  2. ^ Salomon, David (февраль 1993) [1992]. Написано в Калифорнийском государственном университете, Нортридж, Калифорния, США. Chivers, Ian D. (ред.). Assemblers and Loaders (PDF) . Ellis Horwood Series In Computers And Their Applications (1-е изд.). Чичестер, Западный Суссекс, Великобритания: Ellis Horwood Limited / Simon & Schuster International Group . ISBN 0-13-052564-2. Архивировано (PDF) из оригинала 2020-03-23 ​​. Получено 2008-10-01 .(xiv+294+4 страницы)
  3. ^ Jacob, Bruce; Ng, Spencer W.; Wang, David T.; Rodrigez, Samuel (2008). "Часть I Глава 3.1.3 Оптимизации локальности в режиме онлайн: динамическое сжатие инструкций и данных". Системы памяти: кэш, DRAM, диск . Серия Morgan Kaufmann по архитектуре и проектированию компьютеров. Morgan Kaufmann Publishers / Elsevier. стр. 147. ISBN 978-0-12-379751-3.(900 страниц)
  4. ^ ab Jones, Douglas W. (2018). "Лекция 7, Объектные коды, загрузчики и компоновщики - Последние шаги на пути к машинному коду". Операционные системы, весна 2018 г. Часть коллекции операционных систем CS:3620. Университет Айовы , кафедра компьютерных наук. Архивировано из оригинала 2020-06-06 . Получено 2020-06-06 .
  5. ^ ab Boehm, Elaine M.; Steel, Jr., Thomas B. (июнь 1958 г.). Machine Implementation of Symbolic Programming - Summary of a Paper to be Presented at the Summer 1958 Meeting of the ACM. ACM '58: Preprints of papers performed at the 13th national meeting of the Association for Computing Machinery. стр. 17-1–17-3. doi :10.1145/610937.610953. Архивировано из оригинала 06.06.2020 . Получено 06.06.2020 .(3 страницы)
  6. ^ abc Boehm, Elaine M.; Steel, Jr., Thomas B. (апрель 1959 г.). «Система SHARE 709: машинная реализация символического программирования». Journal of the ACM . 6 (2): 134–140. doi : 10.1145/320964.320968 . S2CID  16545134. стр. 137–138: […] Есть интересная особенность, связанная с кодированием символов для включения в словарь. В обычном режиме выражения символы могут быть составлены из набора из 50 символов. Если бы кодирование было посимвольным, для представления каждого такого символа потребовалось бы шесть бит. Поскольку символ может содержать до шести символов, для представления каждого символа потребовалось бы в общей сложности 36 бит. Это может показаться удобным, так как длина слова 709 составляет ровно 36 бит, но минутное размышление показывает, что это неудачно, так как было бы желательно иметь бит или два, доступные в том же слове, что и представление символа, давая ключ к природе символа. Эти биты маркировки могут быть получены. Пусть каждый возможный символ представляет цифру в системе счисления с основанием пятьдесят . Теперь шесть символов символов могут быть прочитаны как натуральные числа в системе с основанием пятьдесят. Если эти числа преобразуются в обычную систему с основанием два, для максимального числа требуется всего 34 бита, и достигается выигрыш в два бита маркировки. Это имеет побочную особенность уменьшения необходимого количества бит для представления всего кода, но время преобразования значительно перевесило бы экономию, если бы не особая длина слова 709. Вот наглядная иллюстрация критического влияния точных спецификаций соответствующей машины на детали схемы кодирования. […](7 страниц)
  7. ^ Shell, Donald L. (апрель 1959 г.) [октябрь 1958 г.]. «Система SHARE 709: совместные усилия». Журнал ACM . 6 (2): 123–127. doi : 10.1145/320964.320966 . S2CID  16476514.(5 страниц)
  8. ^ "IBM 7090 Data Porcessing System General Information" (PDF) . IBM. 1959. стр. 12–13. G22-6505-.
  9. ^ Эрман, Джон Роберт; Снайдер, Джеймс Н. (1964-04-15). "3.3.2.1 SCAT". Исполнительная система PORTHOS для IBM 7094 - Руководство пользователя (PDF) . Университет Иллинойса , Лаборатория цифровых компьютеров аспирантского колледжа. Архивировано (PDF) из оригинала 2020-06-07 . Получено 2020-06-07 . […] SCAT - это двухкомпонентный ассемблер, который вкратце работает следующим образом: программы, написанные символически как один заказ на карту, усваиваются на первом этапе "компилятором", который сканирует программу на наличие символов и выводит сжатую колоду карт (колоду SQUOZE), содержащую таблицы этих символов и сжатую и эффективно закодированную программу. Во время второй фазы эта колода SQUOZE поглощается программой «изменить и загрузить», которая преобразует объектную программу в двоичный машинный язык, который по выбору может быть загружен готовым к запуску или выведен на абсолютные двоичные карты (23 порядка на карту) для загрузки и запуска в более позднее время. «Листер» может создать печатную версию программы на любой из этих стадий. Символические исправления в программу могут быть вставлены во вторую фазу вместе с колодой SQUOZE. […]
  10. ^ Справочное руководство SOS (PDF) . IBM . Ноябрь 1959 г.
  11. ^ "8.10 .RAD50". PAL-11R Assembler - Programmer's Manual - Program Assembly Language and Relocatable Assembler for the Disk Operating System (2nd revision printing ed.). Maynard, Massachusetts, USA: Digital Equipment Corporation . May 1971 [February 1971]. p. 8-8. DEC-11-ASDB-D . Retrieved 2020-06-18 . p. 8-8: […] Программы для систем PDP-11 часто обрабатывают символы в специально закодированной форме, называемой RADIX 50 (эту форму иногда называют MOD40 ). Эта форма позволяет упаковать 3 символа в 16 бит […][3]

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