Задача, которую я хочу предложить, затрагивает вопросы передачи произвольных двоичных данных по текстовым каналам.

Есть некий набор строк.
Как и в предыдущей задаче, в строках могут быть использованы любые символы.
Бывают случаи, когда такой набор данных нужно передать через транспортный канал, который умеет транслировать только определенный алфавит.
Одним из решений такой поблемы (например в почтовых стандартах) является применение методики кодирования base64, при которой алфавитом из 64 символов передаются любые бинарные (т.е. из байтов со значениями 0..255) данные. Строки при этом, как известно вырастают на величину (log(256)/log(64)-1)*100% = 33% по стравнению с исходной длиной.

Основное требование:

Но вот представьте себе ситуацию: заказчик сказал, что накладные расходы в 33% его не устраивают. Он предлагает использовать алфавит из 85 символов текста, и согласен на рост в (соответственно (log(256)/log(85)-1)*100% ) 25% от исходной длины. И ни байтом больше.
Требуется написать такие функции $text = user_encode($data, $abc) и $data = user_decode($text, $abc), которые бы кодировали и декодировали указанные данные ($data) в текст ($text) символами из строки с предложенным алфавитом ($abc), и укладывались в 25% overhead.

Дополнительные требования:

Еще заказчик сказал, что
б) кодированные строки он собирается не только пересылать, но и хранить. И ему было бы крайне удобно если результаты строкового сравнения на больше меньше равно оригинальных данных и кодированных строк были равнозначными.
То есть если данные1< данные2 то и код1< код2 .

б) поскольку часть интерфейсов, работающих с таким представлением данных, позже вероятно будет реализована на других языках, а возможно даже в микроконтроллере, ему бы не хотелось, чтобы в реализации user_encode и user_decode не применялись какие-либо стандартные функции, отличные от ord, chr, substr, strpos и intval, и крайне желательно, чтобы было исключено применение операций с плавающей точкой.

Чтобы исключить предвзятость в оценке, логическая сторона решения будет оцениваться следующим скриптом, начисляющим штрафные баллы за невыполненные требования.

Стилистика тоже будет оценена.
Возможно, я напишу обложку для оценки быстродействия, но акцентировать на этом аспекте внимание не стоит. Задача и без того непростая. :)

Примерный проверочный скрипт

<form method=post action = ?> Алфавит: <input size=100 name=abc value="abcdefghijklmnopqrstuvwxyzABCDEFGHI JKLMNOPQRSTUVWXYZ0123456789!@$^*()[],./_+-=~:|?{}`"> <br>Строки данных:<br> <textarea cols=100 rows=10 name=list > A  Quicks brown fox jumps over lazy dog !! </textarea> <br><input type=submit value=Go /> </form> <hr> <?php include 'user.php'; // function user_encode($data, $abc) // { // ... // } // function user_decode($text, $abc) // { // ... // } //function user_encode($x, $abc) {return  base64_encode($x); } //function user_decode($x, $abc) {return base64_decode($x); }     if(!isset($_POST['list'])|| @strlen($_POST['abc'])<2) exit;     $list = get_magic_quotes_gpc()? stripslashes($_POST['list']):$_POST['list'];     $abc = get_magic_quotes_gpc()? stripslashes($_POST['abc']):$_POST['abc'];     $list = explode("\r\n", $list);     echo "<table border=1>";     $maxres = 0;     foreach($list as $msg)     {         if(isset($dm))   { $dm0 = $dm; $em0 = $em; }         if(strlen($msg) > 0 && $msg[0] == ' ')             $msg = base64_decode($msg);         $em = user_encode($msg, $abc);         $dm = user_decode($em, $abc);         $res = '';         if($msg !== $dm) $res = '64 - данные не декодировались';         else         {           $abc0 = count_chars($abc,1);           $abc1 = count_chars($em,1);           $extra = '';           foreach($abc1 as $key =>$val)             if(!isset($abc0[$key]))              $extra .= sprintf(" %02X", $key);           if(strlen($extra))             $res = "32 - применены символы не из алфавита, с кодами $extra";           else           {             $l1 = strlen($dm);             $l2 = strlen($em);             $max = floor(($l1*8 * 1.25 + 7)/8);             if($l2 > $max)                $res = "16 - код длинее оптимального на ".($l2 - $max)."  байт";             else if(isset($dm0))             {               $cmp = ($dm0 < $dm) !== ($em0 < $em);               if($cmp)                 $res = "8 - сравнение кодов не соответствует сравнению данных";             }           }         }         $maxres |= intval($res);         echo "<tr>"                 ."<td>".htmlspecialchars($msg)."</td>"                 ."<td>".htmlspecialchars($em)."</td>"                 ."<td>".htmlspecialchars($dm)."</td>"                 ."<td>.  $res</td></tr>";     }     echo "</table> Штрафных баллов : ".$maxres; ?>

Вы еще с cheops'ом не договорились?

Нет. :)
Насчет чего?

Насчет того, чтобы форму для ответа добавить :)

cheops может её не утвердить.
Сама по себе форма врядли поспособствует решению. :))
И я очень сомневаюсь, что она понадобится раньше, чем через сутки - задача непростая.

Если есть замечания по формулировке, замеченные неточности, непонятные места - прошу высказываться.

Помните недавнюю (относительно) тему? У меня уже готово решение :)

этой задачи? и сколько очков показывает тест?

или предыдущей? тогда его имеет смысл отправить в соответствующую ветку.

Этой, задачи. Та задача мне не понравилась тем, что не требует мозгов.
Мои функции Ваш тест пока не проходили, сейчас внешний вид кода просто привожу в порядок :))

>Этой, задачи. Та задача мне не понравилась тем, что не требует мозгов.
И тем не менее, корректно её никто не решил. Я уже не говорю о том, чтобы с блеском.

>Мои функции Ваш тест пока не проходили, сейчас внешний вид кода просто привожу в порядок :))

надеюсь, требованию по неприменению плавучки и стандартных функций, Ваш код удовлетворяет?

по неприменению плавучки
Удовлетворяет.

стандартных функций
Исправляю.

>по неприменению плавучки
>Удовлетворяет.

Респект. По моему опыту - это одно из самых тяжелых требований в местном контексте.

Ммм..Сейчас вернулся к скрипту. Проверил и ... 72 штрафных очка! А все потому что мой скрипт расчитан только на кол-во символов в "алфавите" кратное двум. Это придется переписывать...

Задача поставлена не корректно. Это просто невозможно.
В base64 из 3 символов получают 4 всегда. И из за этого выполняется 1 условие ( о равенстве данных и кода). Потому что 256 "делиться" на 64. А вот 256 на 85 не делиться :) а значит либо код будет терпеть большие потери (сократить алфавит) либо какие-то символы будут кодироваться по 3 байта а какие-то по 4 а это не даст правильных результатов на равенство.

Я не просто так строку с логарифмами привел. Математически задача корректна абсолютно.
85ю символами можно передать данные с 25% нагрузкой при очень незначительной избыточности, вызванной нестрогим равенством в тех уравнениях.
256 на 64 не делится. Просто и 256 и 64 являются степенями двойки. Но это (хотя и изрядно облегчает жизнь) совсем необязательно для кодирования.
Подсказка. попробуйте разбивать данные не по три байта, а по четыре.
А еще попробуйте подумать, откуда вообще взялось слово base в названии метода.
На самый худой конец, за требование переносимости сравнения можно не браться, хотя задача потеряет без него некоторый шарм.
Если формировать код переменной длины (в том смысле, как вы говорите : где 3 - где 4) - это только изрядно запутает и усложнит решение. Лично я собираюсь обойтись без этого - у меня все данные длины m породят код длины n, где m и n - константы, связанные уравнением из тестового скрипта с точностью до байта вверх. И проверка это подтверждает.

Исправил ошибки. 8 штрафных баллов. Trianon, а у Вас 0 на данный текст?

пока 8.
лениво доделывать....

А приблизительная скорость кодирования? Например, для 1000 символов.

Вот такой довесок:

<?     $z=$y=$x='';     for($x='.', $l = 0; $l < 256; $l++)     $x.= chr($l);     for($k = 0; $k < 256; $k++)       $y .= $x;     for($k = 0; $k < 256; $k++)       $z .= $y;     $tm = microtime(1);     base64_encode(base64_encode(base64_encode(base64_encode(base64_encode($z)))));//, $abc);     $tm1 = microtime(1)-$tm;     $z = '';     $tm = microtime(1);     $p = user_encode($y, $abc);     $tm2 = (microtime(1)-$tm)/$tm1;     $tm = microtime(1);     $q = user_decode($p, $abc);     $tm3 = (microtime(1)-$tm)/$tm1;     echo "=== encode $tm2 === decode $tm3 === <br/>\r\n"; ?>

Показывает === encode 0.500454996634 === decode 0.424577800607 ===
Я попытался отнормировать результат по быстродействию процессора на base64_encode;

но на доделанном варианте будет хуже....

Быстро. Относительно...

там коэффициент 1:1280

А у Вас сколько?

Сейчас не у компа.
Но даже если был, то, думаю, не сказал бы...
У меня создалось впечатление, что скорость кодирования моей функции возрастает в геометрической прогрессии.
К тому же, мой скрипт в данный момент никак не удовлетворяет условию о стандартных функциях. Еще поищу другие решения.

substr и strpos - добавлены.
Я просто забыл про них вначале.

Ой, какие пустяки. Если бы substr() или subpos(). :))
BCmath :(

>Ой, какие пустяки. Если бы substr() или subpos(). :))
>BCmath :(

Н-да... фирма веников не вяжет - фирма делает гробы....

Да ладно Вам. Я как-нибудь до уровня вязания веников дотяну.

256 / 64 = 4
Я проверю мою теорию о возможности на вашем примере. Жду.

>256 / 64 = 4
Touche. :)))
но опять же дело не в делимости

хм, интересненько :)
я решение не написал (мне двойка типа :) ), но подумал над алгоритмом..

Так проблема вот в чем, когда строка заканчивается

|доп символ| |*| |*| |*| |*| |доп символ| |*| |*| |*| |*| =тут все гладко (на 25% больше)
|доп символ| |*| |*| |*| |*| |доп символ| |*| |*| =а тут не совсем, можно ли дописать еще символ? (но тогда будет больше 25%)

можно ли дописать еще символ
Зачем? :)

но тогда будет больше 25%
И так больше - 6 символов было, стало 8. 33,(3)%.

echo base64_encode('a'); // YQ==
было 1 стало 4.

еще тут
abcdefghijklmnopqrstuvwxyzABCDEFGHI JKLMNOPQRSTUVWXYZ0123456789!@$^*()[],./_+-=~:|?{}`
86 символов. надо 85 ?

"=" не в счет. Этот символ может появится только в конце строки и он нужен для того, чтобы показать сколько байтов не хватает для 3 к 4. "a" - 1 байт, не хватает двух, след. два "=".

еще тут
...
86 символов. надо 85 ?
Вы скопировали вместе с пробелом. Он появился из-за защиты дизайна.

понятно )

>echo base64_encode('a'); // YQ==
>было 1 стало 4.

Терминирующие знаки = для работы алгоритма base64 не нужны. Они добавлены лишь красоты ради. Ну и чтобы можно было слегка упростить код на краевых случаях.

Объясните тупому как работает Base64.
Есть символы из диапазона 0...256. Их нужно перепаковать в символы с более узким интервалом (0...64). Но так как 256/64=4, то символы из первого диапазона будут занимать в 4 раза больше места, а не на 33%, как писали выше.
Например, имеем chr(137). Разобью 0...256 на интервалы 0-64, 65-128, 129-192 и 192-256. Тогда chr(137) будет занимать 4 символа 64-ричного алфавита с номерами: 64, 64, 55, 0.
Объясните пожалуста, как можно запаковывать информацию более экономично

Почему мои новые сообщения стали появляться посередине страницы, а не в конце как раньше было? Это только у меня такой глюк?

>Есть символы из диапазона 0...256.
То есть байты. 0...255 . Считать нужно точнее.


>Их нужно перепаковать в символы с более узким интервалом (0...64).
0...63 . Считать нужно точнее.

> Но так как 256/64=4, то символы из первого диапазона будут занимать в 4 раза больше места, а не на 33%, как писали выше.

Очень странный вывод.
Вот, к примеру, шестнадцатеричная цифра - это грубо говоря символ с интервалом 0...15
256/16 = 16. Но для представления одного байта достаточно двух таких цифр, а не шестнадцати.

Делить надо не основания . Делить надо логарифмы оснований.

Все не так, как Вы думаете.

Например, слово "softtime":

01110011 01101111 01100110 01110100 01110100 01101001 01101101 01100101

А вот "алфавит" base64.

000000 - A 000001 - B 000010 - C ... 111111 - /

Можно сказать, "шестибитовые" байты. Просто старшие два бита равны нулю.

Деление "3 к 4":

011100 110110 111101 100110 011101 000111 010001 101001 011011 010110 0101

Теперь замена этих "шестибитовых" байтов на символы из "алфавита":

011100 - c 110110 - 2 ...

В итоге: c29mdHRpbWU

Так как для "чистого" деления "3 к 4" не хватило 1 байта (softtime - 8 символов), то можно приписать "=": c29mdHRpbWU=

Спасибо. Теперь понятно. Моя ошибка была в том, что я пытался перевести текст из 256-значного алфавита в 64-значный напрямую, без использования двоичной системы счисления

А сколько времени хотите отвести на решение задачи?

неделю ... 10 дней.

Задача добавлена в список задач - время пошло. В ночь с четверга (21.06.07) на пятницу (22.06.07), они будут автоматически размещены на форуме и каждый ответ будет оценён по трём критериям (стиль, скорость и количество штрафных баллов). Победитель получает приз - 1 месяц хостинга http://www.st-host.ru.

Ответы следует оставлять в специальной HTML-форме по ссылке.

Я сдал решение. Вы его получили? У меня ответного сообщения никакого не было. Это нормально?
Собираюсь часть лета провести далеко от дома, так что возможно в обсуждении не удастся поучаствовать. Да и решение узнаю с опозданием.
Но задача мне понравилась. Отличная идея у Трианона - сразу указывать какие функции использовать при решении задачи! А то список функций в PHP большой - не знаешь то ли задачу решать, то ли список перечитывать... А так на тренировочных задачках можно закрепить понимание основных функций - это создаёт устойчивую базу под ногами для дальнейшего продвижения! :)
Нетерпится посмотреть какой код другие участники сочинили!

это нормально.
То есть это ненормально, конечно же, но это так.

Да, ваше решение зарегистрировано.

Eugene77, сколько баллов показывает проверочный скрипт Trianon'а?

У меня тут в спешке не было возможности его как следует протестировать, но первая проба вроде нуль показала.

И ещё хочу добавить, что хорошо бы ещё один критерий оценки результатов оговорить в явном виде: коментированность кода.
Если постить код без должных коментариев, то затея теряет смысл. Это же учебный раздел!
Поэтому коментарии должны быть ясны начинающим изучать PHP.
Кстати, в ваших книжках в основном нормальные коментарии, так что вы сумеете разумную оценку дать по этой теме.
Потом можно будет ещё одну очень полезную книжку издать: Задачи и варианты их решений на PHP. Где для каждой задачки публиковать разные варианты решений. Удобно - коментарии добавлять не придётся.
Хотя конечно, для книги другие требования к коментариям, чем для программы. В книге, например, надо пояснять что делают стандартные функции, а сидя за комп., листаешь мануал...

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

>Хотя конечно, для книги другие требования к коментариям, чем для программы. В книге, например, надо пояснять что делают стандартные функции, а сидя за комп., листаешь мануал...
Тем самым можно набить 700 страниц для любой книжки, что иногда и требуется :)

Я полагаю, по 10 штрафных баллов можно дать за использование умных функций, плавучки и т.п.
Ну и пределах семи штрафных очков Вы можете набросить от имени жюри .
Собственно, можете и больше - но в рамках призового фонда. :))

Кстати, проверочный скрипт Трианона, кажется не совсем корректно работает.
Формула

$max = floor(($l1*8 * 1.33 + 7)/8);

для строки длинной в 4 байта даёт 6, а не 5 . Как ожидается из предшествующих рассуждений.

Можно её заменить, например, на такую строку, может и более длинную, зато с более прозрачной логикой, как мне кажется.

$ll=$l1%4;    $max = 5*(int)($l1/4) +(int)($ll*($ll+3)/($ll+1));

Отдельно вычисляется длина целых четвёрок байтов и длина остатка от деления на четыре.

$max = floor(($l1*8 * 1.33 + 7)/8); - это на 33 процента тест. Для base64_encode
Для проверки решений на 25 процентов эта строка будет выглядеть так:

$max = floor(($l1*8 * 1.25 + 7)/8);

Суть теста в том, чтобы закодированная строка с не превышала исходную более чем на 25 % (округляя до байта вверх).

strlen() тоже относится к простым?
pow()?

P.S. list() функцией не является, поэтому, думаю, за нёё штрафные баллы начислять не будут.

strlen - да. В php это даже не функция, а build-in свойство объекта.

pow - нет. pow там нафиг не нужен. Но ход Ваших мыслей мне нравится.

Я готов разрешить использовать функцию sort для лексикографического упорядочения алфавита. Только потому, что сам забыл его упорядочить в тестере.

В конце концов - задача не про сортировку...

Ах, сколько чудных задач можно про сортировку написать....

Просто, к сожалению, в PHP оператора возведения в степень не ввели. А в Perl, к примеру, ввели. А в самом коде писать это некрасиво. А под отдельную ф-ю выводить нельзя.
О sort(), наоборот, даже не спрашивал, т.к. посчитал "умной функцией". Хорошо, буду использовать ее.

Боже упаси.
Я не запрещал использование своих собственных функций. Запрещены лишь стандартные - потому что у стороннего разработчика их может просто напросто не найтись.
Если Вы знаете как реализовать pow (или любую другую функцию) - напишите собственную.

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

Кстати, посылать в качестве ответа только функции? Никаких тестов и демонстраций не надо?

Функций с указанными именами должно быть две, иначе тестер их не найдет.
Своих собственных функций, классов, методов - на усмотрение автора. Влиять будет на стиль, читабельность, быстродействие.

Отправлять же Вы вольны всё что угодно, в том числе тесты, демнострации, комментарии.

Тема уже очень длинная, давайте начнём новую ветку

http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39219