?

Log in

No account? Create an account

Внезапно нетранзитивное - Общество дровосеков Бердичева по изучению Мишны

Aug. 18th, 2017

01:27 am - Внезапно нетранзитивное

Previous Entry Share Next Entry

В былые времена символов в кодировках было немного, и поэтому, хотя в байте уже было 8 бит, о возможности наличия байтов с установленным старшим битом в нормальных человеческих текстовых строках (а не, скажем, в сжатом представлении) никто не заботился. От этого, как говорится, байты с установленным старшим битом служили неиссякаемым источником лулзов.

В приведенной программе подчеркивание внутри строк аналогично символу обратной косой черты в языке Си. Тип ALFA - массив символов, умещающийся ровно в одно машинное слово.


 00001    1  0  PROGRAM MAIN(OUTPUT);
 00001    2  1  VAR A,B,C:ALFA;
 00007    3  2  BEGIN
 00010    4  2  A := ’_000_000_000_000_000_000’;
 00011    5  2  B := ’_200_000_000_000_000_000’;
 00012    6  2  C := ’_177_177_177_177_177_177’;
 00013    7  2  WRITELN(A > B, B > C, C > A);
 00050    8  0  END.
           *EXECUTE
    TRUE    TRUE    TRUE


Предлагается представить себе и ужаснуться, что могло происходить с сортированными контейнерами, если в них помещали подобные строки.

В качестве задания со звездочкой предлагается подумать, как могла была быть устроена система команд, приводящая к такому парадоксальному результату.

This entry was originally posted at http://spamsink.dreamwidth.org/1058374.html. Please comment there using OpenID.

Comments:

[User Picture]
From:archaicos
Date:August 18th, 2017 10:48 am (UTC)
(Link)
А что сравнение сравнивает? Целиковые слова? Или типа пытается делать алфавитное посимвольное сравнение? И где более значимый конец, а где менее?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 18th, 2017 03:07 pm (UTC)
(Link)
Благодаря тому, что выбранный порядок символов в слове - big-endian, и тому, что в Паскале строки всегда начинаются на границе слова, сравнение строк реализовано как сравнение целых слов, и при отсутствии байтов с установленным старшим битом выдает правильный результат лексикографического сравнения.

Было бы еще понятно, если бы просто старшие байты в слове сравнивались как signed, а остальные - как unsigned, но здесь хитрее.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:August 19th, 2017 12:04 am (UTC)
(Link)

А если старший бит определяет, целое там или вещественное и сравнение целых с вещественными не определено? Или там кусок экспоненты? Или это и вовсе какой-то NaN или tag?

(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 19th, 2017 01:56 am (UTC)
(Link)
Нет, там всё тривиально. Никаких тегов, обычный старый плавающий формат без скрытого бита. Хитрость в том, что для сравнения полноразрядных строк используется не плавающее вычитание — потому, например, что оно могло дать переполнение, а другие команды.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:September 8th, 2017 07:58 pm (UTC)
(Link)
Ответ таков: для сравнения целиковых слов применяется команда циклического (оно же 1's complement) сложения, перед которым один из операндов XORится со всеми единицами, и результат сравнения определяют по старшему разряду.
(Reply) (Parent) (Thread)