Главная страница IT-студия  
PHP на примерах (2 издание). Авторы: Кузнецов М.В., Симдянов И.В. PHP 5/6. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель PHP 5 / 6 (3 издание). Авторы: Кузнецов М.В., Симдянов И.В. PHP. Практика создание сайтов. Авторы: Кузнецов М.В., Симдянов И.В. Головоломки на PHP для хакера (второе издание). Авторы: Кузнецов М.В., Симдянов И.В. Объектно-ориентированное программирование на PHP. Авторы: Кузнецов М.В., Симдянов И.В. MySQL на примерах. Авторы: Кузнецов М.В., Симдянов И.В. C++. Мастер-класс в задачах и примерах. Авторы: Кузнецов М.В., Симдянов И.В. Социальная инженерия и социальные хакеры . Авторы: Кузнецов М.В., Симдянов И.В. PHP. Народные советы. Авторы: Кузнецов М.В., Симдянов И.В. MySQL 5. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель PHP 5 (второе издание). Авторы: Кузнецов М.В., Симдянов И.В. Программирование: ступени карьеры. Авторы: Кузнецов М.В., Симдянов И.В. PHP Security & Cracking Puzzles. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель MySQL 5. Авторы: Кузнецов М.В., Симдянов И.В.
Консультации от известных специалистов и авторов многих книг

Информационный портал
«SoftTime-INFO»




| Задачи | 22. Кодирование и декодирование данных (11.06.2007).

22. Кодирование и декодирование данных (11.06.2007).

Автор - Trianon
Категория - 3

Имеется некий набор строк, содержащие произвольные символы. Набор предназначен для передачи через транспортный канал, который способен транслировать только определенный алфавит.

Одним из решений такой поблемы (например в почтовых стандартах) является применение методики кодирования 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.

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

a) кодированные строки заказчик собирается не только пересылать, но и хранить. И ему было бы крайне удобно если результаты строкового сравнения на больше меньше равно оригинальных данных и кодированных строк были равнозначными. То есть если данные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!@$^*()[],./_+-=~:|?{}'"> 
Строки данных: 
<textarea cols=100 rows=10 name=list > 

 Quicks 
brown 
fox 
jumps 
over 
lazy 
dog 
!! 
</textarea> 
<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) > && $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*1.33 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
?>

Решение и обсуждение задачи доступно по ссылкам
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=38855
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39219
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39444
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39445
http://www.softtime.ru/forum/read.php?id_forum=7&id_theme=39446

Русская версия English

 
  Rambler's Top100 Яндекс.Метрика Яндекс цитирования