PRB: реализация HEX atoi - Этюды для программистов

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее ;) ):

F>Условия:

F>3. Знак числа должен сохраняться.

Гекс со знаком — оу е!

F>4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

Халява сэр

F>6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).

А "0x123456789" = 0x12345678 или 0x23456789 ?

F>7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).

F>8. Запрещается использовать операторы continue и goto в цикле.
F>10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

Любим усложнять жизнь?

int hexatoi(const char* str)
{
  if(!str) return 0;

  int v = 0; // аккумулятор
  bool n = false; // негатив
  char c = *(str++); // пригодится

  // ожидаем пробелы
  while(c == ' ' || c == '\t') c = *(str++);
  if(!c) return 0;

  // ожидаем знак
  // на мой взгляд, так эффективнее, чем громоздить n = (...) ? (...) : (...)
  if(c == '-') { n = true; c = *(str++); }
  else if(c == '+') c = *(str++);
  if(!c) return 0; // В принципе, эту проверку можно опустить. Но она быстрая, облегчит жизнь маломало

  // ожидаем префикс
  // а если это просто 0, то и бог с ним. Не жалко
  if(
    c == '0' &&
    (((c = *(str++)) == 'x') || (c == 'X'))
  ) c = *(str++);

  // ожидаем цифры
  // кто не верит оптимизатору, пусть напишет 55 вместо 'A'-10...
  while(
    (с >= '0' && c <= 'f') && // оптимизирующая проверка - для быстрого отсечения неправильных символов
    ( // повторные проверки c>='0',c<='f' оставлены "для наглядности" (или если убрать оптимизирующую)
      (c >= '0' && c <= '9') && (v <<= 4, v += (c - '0'       ), true) ||
      (c >= 'A' && c <= 'F') && (v <<= 4, v += (c - ('A' - 10)), true) ||
      (c >= 'a' && c <= 'f') && (v <<= 4, v += (c - ('a' - 10)), true)
    )
  ) c = *(str++);

  return n ? -v : v;
}

Здравствуйте, Кодт, Вы писали:

К>О! Новая задачка. Представьте себе, что для различения используется не префикс, а суффикс (b/inary,d/ecimal,h/ex).
а где ответы? тихо как-то...

можно я лишь алгоритм?
— конвертируем строку в число, используя максимально возможную базу (hex в данном случае) [база1]
— попутно отмечаем, цифры каких баз встретились (максимум)
— когда доходим до последнего символа [база2] — проверяем, все ли цифры, нам встретившиеся, соответствуют базе2
— теперь вместо строки разбираем число:

извлекаем цифру из временного результата с помощью базы1 [ digit = temp_result % base1 ]
добавляем цифру к результату с помощью базы2 [ result += digit * pow(base2, index) ]

мне просто интересно знать: правильные ли у мня мысли

SD>- конвертируем строку в число, используя максимально возможную базу (hex в данном случае) [база1]
SD>- попутно отмечаем, цифры каких баз встретились (максимум)
SD>- когда доходим до последнего символа [база2] — проверяем, все ли цифры, нам встретившиеся, соответствуют базе2
SD>- теперь вместо строки разбираем число:
SD>

SD>

извлекаем цифру из временного результата с помощью базы1 [ digit = temp_result % base1 ]
SD>

добавляем цифру к результату с помощью базы2 [ result += digit * pow(base2, index) ]
SD>

Так на каком-нибудь длинном binary можно и переполнение получить. Надо ещё смотреть на длину пропарсенной строки, если она превосходит порог — понижать базу1, попутно пересчтывая число.

... << RSDN@Work 1.1.3 stable >>
Pink Floyd — Wearing The Inside Out
Standarts are great, everyone should have one!

Итак, задача номер два (посложнее

):

Задача:

Написать функцию, которая конвертирует строку (char*), содержащую число в шестнадцатеричном представлении (HEX) в число (int), то есть реализацию atoi для чисел в шестнадцатеричной системе счисления. Прототип функции:

int hex_atoi(const char* hex_string);

Условия:

0. Язык программирования — С/С++.

1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.

2. Пробельные символы в начале строки (пробел и символ табуляции — \t) опускаются.

3. Знак числа должен сохраняться.

4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

5. Передаваемая строка содержит числа в шестнадцатеричном формате.

6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).

7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).

8. Запрещается использовать операторы continue и goto в цикле.

9. Количество вспомогательных переменных ограничено тремя.

10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

Набор тестов:

hex_atoi("0x3107")         =  12551
hex_atoi(" \t 3107")       =  12551
hex_atoi("0x-3107")        =  0 
hex_atoi("0+x3107")        =  0
hex_atoi("0xa0")           =  160
hex_atoi("0xA1")           =  161
hex_atoi("a0")             =  160
hex_atoi("A1")             =  161
hex_atoi("A0a0t54")        =  41120
hex_atoi("ABCDEF")         =  11259375
hex_atoi("qABCDEF")        =  0 
hex_atoi("0A0")            =  160
hex_atoi("xA0")            =  0
hex_atoi("FFFFFFFF")       = -1
hex_atoi("-FFFFFFFF")      =  1 
hex_atoi("+0x12")          =  18
hex_atoi("-0x12")          = -18
hex_atoi("+a")             =  10
hex_atoi("-a")             = -10
hex_atoi("0")              =  0
hex_atoi(NULL)             =  0

Дерзайте!

07.07.05 14:37: Перенесено из 'Исходники'

За основу взял Ваш код new_atoi

Вот не оптимизированный вариант.
Дальше думаю


int hex_atoi(const char* string)
{
    if(!string) 
        return 0;
    int result = 0;
    
    while(*string == ' ' || *string == '\t')    
        string++;

    bool bNegativeSign = (*string == '-');
    if(bNegativeSign || *string=='+') string++;

    if ((*string == '0') && (*(++string) == 'x'))
        string ++;

    while (*string)
    {
        if (((*string < 48) || (*string > 57)) &&
            ((*string < 'a') || (*string > 'f')) &&
            ((*string < 'A') || (*string > 'F')))
            break;
        result *= 16;
        if ((*string > 48) && (*string < 57))
        {
            result += *string - 48;
        }
        if ((*string >= 'a') && (*string <= 'f'))
            result += *string - 'a' + 10;
        if ((*string >= 'A') && (*string <= 'F'))
            result += *string - 'A' + 10;
        string++;
    }
    return ( bNegativeSign ? -result : result );
}

Если и дальше заняться плагиатом, то из кода глубокоуважаемого oranry
Можно получить следующее

Сам бы во век до такого не додумался

int hex_atoi(char *s)
{
    int sign=1, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++), 1);
    if ((*s == '0') && (*(++s) == 'x')) s++;
    while ((*s>='0' && *s<='9') || (*s>='A' && *s<='F') || (*s>='a' && *s<='f'))
    {
        val*=16;
        if (*s>='0' && *s<='9') val+=*s++ - 48; 
        if (*s>='a' && *s<='f') val+=*s++ - 'a' + 10; 
        if (*s>='A' && *s<='F') val+=*s++ - 'A' + 10; 
    }
    return val*sign;
}

Насчет вариантов 48 + 9 -ну лень калькулятор доставать

int hex_atoi(const char *string)
{
    int sign = 1, value = 0;

    if( string )
    {
        while(*string == ' ' || *string == '\t') string++;
    } 
    else
    {
        return 0;
    }

    if( *string == '+' || *string == '-' )
    {
        sign = (*string == '+') ? 1 : -1;
        string += 1;
    }

    if( *string == '0' && (*(string+1) == 'x' || *(string+1)== 'X') )
    {
        string += 2;
    }

    while( *string )  
    {
        if( *string >= '0' && *string <= '9' )
        {
            value = (value << 4) + (*string - '0');
        }
        else
        if( *string >= 'a' && *string <= 'f')
        {
            value = (value << 4) + (*string - 'a' + 10);
        } 
        else
        if( *string >= 'A' && *string <= 'F' )
        {
            value = (value << 4) + (*string - 'A' + 10);
        } 
        else
        {
            return value * sign;
        }
        string++;
    }

    return value*sign;
}

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):

Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.

Здравствуйте Vampire, Вы писали:

V>Здравствуйте Flamer, Вы писали:

F>>Итак, задача номер два (посложнее

):

V>Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
V>Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.
V>

Ну так посложнее же

Пусть немножко, но все-же... Обороты надо набирать постепенно

Здравствуйте Flamer, Вы писали:

F>Здравствуйте Vampire, Вы писали:

V>>Здравствуйте Flamer, Вы писали:

F>>>Итак, задача номер два (посложнее

):

V>>Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
V>>Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.
V>>

F>Ну так посложнее же

Пусть немножко, но все-же... Обороты надо набирать постепенно

Ну тогда вот чисто мат. задачка.
Конвертор чисел по любому основанию.
Это значит не только 2 8 10 16, но и любое другое типа 12 и т.п.

Здравствуйте Vampire, Вы писали:

[skipped]

V>Ну тогда вот чисто мат. задачка.
V>Конвертор чисел по любому основанию.
V>Это значит не только 2 8 10 16, но и любое другое типа 12 и т.п.

Плз, оформите все это в отдельный тред (опишите условия задачи, еще что-то, в общем, поподробнее) — думаю, будет интересно...

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):

F>Задача:

F>Написать функцию, которая конвертирует строку (char*), содержащую число в шестнадцатеричном представлении (HEX) в число (int), то есть реализацию atoi для чисел в шестнадцатеричной системе счисления. Прототип функции:
F>Условия:
F>0. Язык программирования — С/С++.
F>1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
F>2. Пробельные символы в начале строки (пробел и символ табуляции — \t) опускаются.
F>3. Знак числа должен сохраняться.
F>4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160
F>5. Передаваемая строка содержит числа в шестнадцатеричном формате.
F>6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).
F>7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).
F>8. Запрещается использовать операторы continue и goto в цикле.
F>9. Количество вспомогательных переменных ограничено тремя.
F>10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

почему бы не написать сразу универсальную функцию определяюшюю тип числа по началу записи
0x — HEX
0 — OCT
остальное DEC
соответственно проверяя коректность символов (т.е 0xa => 10, а 0a => 0, a => 0)
условия оставим теже, но немного довавим
1. сделать две функции
а. signed long sig_uni_atoi(const char *str);
учитывеет знак, знаковый бит. при переролнении возврашает 0, (т.е 2147483648 => 0)
б. unsigned long usig_uni_atoi(const char *str);
не учитывеет знак, знаковый бит.
(можно дополнить/исправить)

Здравствуйте, Кодт, Вы писали:

[]

Блин, только что проснулся, т.к. как раз понадобилась такая весчь для одной маленькой библиотечки, где, по условию задачи, 30 Кб CRT-runtime тащить низзя... Долго вкуривал в выделенные жирным строчки... И пришел к выводу — браво, маэстро!

К>

[]

К>    ( // повторные проверки c>='0',c<='f' оставлены "для наглядности" 
        // (или если убрать оптимизирующую)
К>      (c >= '0' && c <= '9') && (v <<= 4, v += (c - '0'       ), true) ||
К>      (c >= 'A' && c <= 'F') && (v <<= 4, v += (c - ('A' - 10)), true) ||
К>      (c >= 'a' && c <= 'f') && (v <<= 4, v += (c - ('a' - 10)), true)
К>    )
К>  ) c = *(str++);

К>  return n ? -v : v;
К>}
К>

Здравствуйте, orangy, Вы писали:

[]
O>Извращаться, так до конца

O>  (val+=*s + (*s>='0' && *s<='9')?-48:((*s>='a' && *s<='f')?10 - 'a':((*s>='A' && *s<='F')?(10 - 'A')))),++s; 
O>

Я давно подозревал, что мсье любитель извращенных отношений

Классно.

Здравствуйте, Flamer, Вы писали:

F>Здравствуйте, Кодт, Вы писали:

F>[]

F>Блин, только что проснулся, т.к. как раз понадобилась такая весчь для одной маленькой библиотечки, где, по условию задачи, 30 Кб CRT-runtime тащить низзя... Долго вкуривал в выделенные жирным строчки... И пришел к выводу — браво, маэстро!

в порядке личного бреда:

#include <stdio.h>

int hex_atoi(const char* str)
{
  if(!str)return 0;
  static int cvt[]={0,1,2,3,4,5,6,7,8,9,-1,-1,-1,-1,-1,-1,-1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,11,12,13,14,15};
  int  res=0;
  bool negative=false;
  while(*str==' ' || *str=='\t')str++;
  while(*str=='-' || *str=='+')if(*str++=='-')negative=!negative;
  if(str[0]=='0' && (str[1]=='x' || str[1]=='X'))str+=2;
  while(*str)
  {
    if(*str<'0' || *str>'f')break;
    if(cvt[*str-'0']==-1)break;
    res=(res<<4)|cvt[*str-'0'];
    str++;
  }
  return negative?-res:res;
}

#define CHECK(expr,val) \
  if((expr)!=(val))printf("failed " #expr "(%d)!=" #val "\n",(expr));else printf("ok " #expr "\n")

int main(int argc,char* argv[])
{
CHECK(hex_atoi("0x3107")         ,  12551);
CHECK(hex_atoi(" \t 3107")       ,  12551);
CHECK(hex_atoi("0x-3107")        ,  0);
CHECK(hex_atoi("0+x3107")        ,  0);
CHECK(hex_atoi("0xa0")           ,  160);
CHECK(hex_atoi("0xA1")           ,  161);
CHECK(hex_atoi("a0")             ,  160);
CHECK(hex_atoi("A1")             ,  161);
CHECK(hex_atoi("A0a0t54")        ,  41120);
CHECK(hex_atoi("ABCDEF")         ,  11259375);
CHECK(hex_atoi("qABCDEF")        ,  0);
CHECK(hex_atoi("0A0")            ,  160);
CHECK(hex_atoi("xA0")            ,  0);
CHECK(hex_atoi("FFFFFFFF")       , -1);
CHECK(hex_atoi("-FFFFFFFF")      ,  1);
CHECK(hex_atoi("+0x12")          ,  18);
CHECK(hex_atoi("-0x12")          , -18);
CHECK(hex_atoi("+a")             ,  10);
CHECK(hex_atoi("-a")             , -10);
CHECK(hex_atoi("0")              ,  0);
CHECK(hex_atoi(NULL)             ,  0);
  return 0;
}

Здравствуйте, Flamer, Вы писали:

F>Дерзайте!

а почему нет реализации для __int64 ?

Здравствуйте, Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):
Работать было влом, дело было днём

int hex_atoi(const char* hex_string)
{
    int res = 0;
    int negative = 0;

    if (hex_string)
    {
        while (*hex_string == ' ' || *hex_string == '\t')
            hex_string++;

        if (*hex_string == '-' || *hex_string == '+')
        {
            negative = *hex_string == '-' ? 1 : 0;
            hex_string++;
        }
    
        if (*hex_string == '0' && (*(hex_string + 1) == 'x' || *(hex_string + 1) == 'X'))
            hex_string += 2;
        
        while (*hex_string)
        {
            res <<= 4;
            if (*hex_string >= '0' && *hex_string <= '9')
                res |= *hex_string - '0';
            else if (*hex_string >= 'A' && *hex_string <= 'F')
                res |= *hex_string - 'A' + 10;
            else if (*hex_string >= 'a' && *hex_string <= 'f')
                res |= *hex_string - 'a' + 10;
            else
            {
                res >>= 4;
                hex_string = "";
            }
            
            hex_string++;
        }
    }
    
    return (negative == 1) ? -res : +res;
}

P.S. Я так догадался, return в цикле тоже нельзя использовать. На всякий случай обощолся без него.

Chez, ICQ#161095094

Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent

Chez wrote:

А чем strtol не устраивает?

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Здравствуйте, MaximE, Вы писали:

ME>Chez wrote:

ME>А чем strtol не устраивает?
Это не то

1) если префикса 0x нет — рассматривает число как десятичное

5. Передаваемая строка содержит числа в шестнадцатеричном формате.

2) возвращает другие результаты в случае ошибок, а надо:

4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

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

1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
...
8. Запрещается использовать операторы continue и goto в цикле.
9. Количество вспомогательных переменных ограничено тремя.
10. Использование конструкции switch, а также цикла do...while (но не while — его можно) запрещается.

Chez, ICQ#161095094

Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent

Здравствуйте, MaximE, Вы писали:

ME>А чем strtol не устраивает?

strtol — это еще ничего, можно пользовать, а на микросососвской strtod я как-то прогорел.

// из strtod.c
        answer = _fltin2( &answerstruct, ptr, (int)strlen(ptr), 0, 0);

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

{
  Author: <EMIT \<a href="mailto:bachin@webceo.com"\>Oleg A. Bachin\</a\>>
  Version: $Revision: 3 $ $Modtime: 14.11.02 10:44 $
}
unit HexUtils;

{$IFOPT O+} 
  {$DEFINE OPTIMIZATION_ON} 
{$ENDIF}

interface

// Конвертация в бинарную строку из шестнадцатиричного фармата
function HexToBin(Source: Pointer; Len: Integer): string; overload;
function HexToBin(Source: string): string; overload;

// Конвертация бинарной строки в шестнадцатиричный фармат
function BinToHex(Source: Pointer; Len: Integer): string; overload;
function BinToHex(Source: string): string; overload;

implementation


function HexToBin(Source: Pointer; Len: Integer): string;
const
  _Hex: array [0..255] of Byte =
    (
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 01,

      02, 03, 04, 05, 06, 07, 08, 09, 00, 00,
      00, 00, 00, 00, 00, 10, 11, 12, 13, 14,
      15, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 10, 11, 12, 13,

      14, 15, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,

      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,

      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
      00, 00, 00, 00, 00, 00, 00, 00, 00, 00,

      00, 00, 00, 00, 00, 00
    );

  {$IFNDEF OPTIMIZATION_ON}
  procedure _HexToBin(Source, Destination: Pointer; Count: Integer); 
  var
    Src, Dest: ^Byte;
  begin
    Src := Source;
    Dest := Destination;
    while (Count > 0) do
      begin
        Dest^ := _Hex[Src^] shl 4;
        Inc(Src);
        Dest^ := Dest^ or _Hex[Src^];
        Inc(Src);
        Inc(Dest);
        Dec(Count);
      end;
  end;
  {$ELSE}
  procedure _HexToBin(Source, Destination: Pointer; Count: Integer); assembler; register;
  asm
          PUSH    ESI                     // Store registers
          PUSH    EDI
          PUSH    EBP

          MOV     ESI, EAX                // Source address
          MOV     EDI, EDX                // Destination address
          MOV     EBP, OFFSET _HEX        // Hex table address

          XOR     EAX, EAX
  @@Loop:
          LODSB                           // High
          MOV     DL, [EBP + EAX]
          SHL     DL, 4
          LODSB                           // Low
          MOV     AL, [EBP + EAX]
          OR      AL, DL
          STOSB                           // Result
          DEC     ECX
          JNZ     @@Loop

          POP     EBP                     // Restore registers
          POP     EDI
          POP     ESI
  end;
  {$ENDIF}

begin
  SetLength(Result, Len);
  _HexToBin(Source, @Result[1], Len);
end;

function HexToBin(Source: string): string;
var
  Len: integer;
begin
  Len := Length(Source) shr 1;
  Result := HexToBin(@Source[1], Len);
end;

function BinToHex(Source: Pointer; Len: Integer): string;
const
  Hex_: array [0..15] of Byte =
    (
      48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
      65, 66, 67, 68, 69, 70
    );

  {$IFNDEF OPTIMIZATION_ON}
  procedure _BinToHex(Source, Destination: Pointer; Count: Integer); assembler; register;
  var
    Src, Dest: ^Byte;
    C: Byte;
  begin
    Src := Source;
    Dest := Destination;
    while (Count > 0) do
      begin
        C := Src^;
        Dest^ := Hex_[C shr 4];
        Inc(Dest);
        Dest^ := Hex_[Src^ and 15];
        Inc(Dest);
        Inc(Src);
        Dec(Count);
      end;
  end;
  {$ELSE}
  procedure _BinToHex(Source, Destination: Pointer; Count: Integer); assembler;
  (*
          EAX = Source
          EDX = Destination
          ECX = Count
  *)
  asm
          PUSH    ESI                     // Store registers
          PUSH    EDI
          PUSH    EBP

          MOV     ESI, EAX                // Source address
          MOV     EDI, EDX                // Destination address
          MOV     EBP, OFFSET HEX_        // Hex table address

          XOR     EAX, EAX
          XOR     EDX, EDX
  @@Loop:
          LODSB
          MOV     DL, AL
          SHR     AL, 4
          MOV     AL, [EBP + EAX]
          STOSB                           // Result
          AND     DL, 15
          MOV     AL, [EBP + EDX]
          STOSB                           // Result

          DEC     ECX
          JNZ     @@Loop

          POP     EBP                     // Restore registers
          POP     EDI
          POP     ESI
  end;
  {$ENDIF}

begin
  SetLength(Result, Len shl 1);
  _BinToHex(Source, @Result[1], Len);
end;

function BinToHex(Source: string): string;
var
  Len: integer;
begin
  Len := Length(Source);
  Result := BinToHex(@Source[1], Len);
end;
  
end.

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Chez wrote:

> ME>А чем strtol не устраивает?
> Это не то

> 1) если префикса 0x нет — рассматривает число как десятичное

Представь, что число идет тебе из командной строки. Как ты различишь без префикса decimal от hex?

> 2) возвращает другие результаты в случае ошибок, а надо:
>

> 4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

Это похоже на то, что делает strtol. http://www.opengroup.org/onlinepubs/009695399/functions/strtol.html

> 3) но самое главное, что задание было поставлено просто как разминка для мозгов !

> 1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
> ...
> 8. Запрещается использовать операторы continue и goto в цикле.
> 9. Количество вспомогательных переменных ограничено тремя.
> 10. Использование конструкции switch, а также цикла do...while (но не while — его можно) запрещается.

Что за идиот это выдумал?

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Здравствуйте, MaximE, Вы писали:

ME>Chez wrote:

>> ME>А чем strtol не устраивает?
>> Это не то

>> 1) если префикса 0x нет — рассматривает число как десятичное
ME>Представь, что число идет тебе из командной строки. Как ты различишь без префикса decimal от hex?
Это понятно.
Но функция, которую я написал, принимает только hex, по условию. И если нет 0x — то рассматривает число как hex, в отличие от strtol.

>> 3) но самое главное, что задание было поставлено просто как разминка для мозгов !

>> 1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
>> ...
>> 8. Запрещается использовать операторы continue и goto в цикле.
>> 9. Количество вспомогательных переменных ограничено тремя.
>> 10. Использование конструкции switch, а также цикла do...while (но не while — его можно) запрещается.

ME>Что за идиот это выдумал?
Здесь!
Я просто выполнил поставленное задание, т.к. делать было больше нечего.

Chez, ICQ#161095094

Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent

Здравствуйте, MaximE, Вы писали:

ME>Представь, что число идет тебе из командной строки. Как ты различишь без префикса decimal от hex?

О! Новая задачка. Представьте себе, что для различения используется не префикс, а суффикс (b/inary,d/ecimal,h/ex).

1. Напишите конвертер, на входе которого — строка в указанном формате (возможно, неправильная), на выходе — число.

2. Напишите конвертер, на входе которого — телетайп (выдающий символы поштучно). Попробуйте обойтись без буферизации в строку.

Здравствуйте, Vampire, Вы писали:

V>

V>int hex_atoi(char *s)
V>{
V>    int sign=1, val=0;
V>    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
V>    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++), 1);
V>    if ((*s == '0') && (*(++s) == 'x')) s++;
V>    while ((*s>='0' && *s<='9') || (*s>='A' && *s<='F') || (*s>='a' && *s<='f'))
V>    {
V>        val*=16;
V>        if (*s>='0' && *s<='9') val+=*s++ - 48; 
V>        if (*s>='a' && *s<='f') val+=*s++ - 'a' + 10; 
V>        if (*s>='A' && *s<='F') val+=*s++ - 'A' + 10; 
V>    }
V>    return val*sign;
V>}
V>

А между прочим ошибка:

строчка "1bC", попав на вход этой функции породит ответ 1 + 11 + 12 = 24, а вовсе и не то, что надо

Всё-таки условия конкурса не совсем удачные. Я бы лучше читабельности и надёжности хотел, а не ребусов на C++

Здравствуйте, DK3981, Вы писали:

SD>>- конвертируем строку в число, используя максимально возможную базу (hex в данном случае) [база1]
SD>>- попутно отмечаем, цифры каких баз встретились (максимум)
SD>>- когда доходим до последнего символа [база2] — проверяем, все ли цифры, нам встретившиеся, соответствуют базе2
SD>>- теперь вместо строки разбираем число:
SD>>

SD>>

извлекаем цифру из временного результата с помощью базы1 [ digit = temp_result % base1 ]
SD>>

добавляем цифру к результату с помощью базы2 [ result += digit * pow(base2, index) ]
SD>>

DK>Так на каком-нибудь длинном binary можно и переполнение получить. Надо ещё смотреть на длину пропарсенной строки, если она превосходит порог — понижать базу1, попутно пересчтывая число.

Можно и с другого конца начать. Изначально установить базу = 2. Каждый раз, встречая неожиданную цифру, повышать базу. Это произойдёт не более 2 раз, поскольку в условии говорилось про (2,10,16). Или не более 3, если добавить восьмеричную.
Ну а если уж на текущей маленькой базе получили переполнение, то с нерассмотренными ещё большими — тем более будет.

Здравствуйте, Oleg A. Bachin, Вы писали:

OAB>ну если вдруг не только в качестве задачки... оптимизированно на скорость, никаких проверок нет.

Я тоже в свое время развлекался, но недооптимизировал, да и
инлайн-асм наложил свои диррективы....

Если будет интересно


#pragma once

//! Конвертация заданного байта в его строково-шестнадцатиричное представление.
/*!
*    \date        2005
*
*    \param[in,out]        al        обрабатываемый байт
*
*    \retval    ah        строково-шестнадцатиричное представление старшей тетрады;
*    \retval    al        строково-шестнадцатиричное представление младшей тетрады.
*
*    \warning
*    ЭТО НЕТРИВИАЛЬНАЯ ФУНКЦИЯ.
*
*    Пролог и эпилог реализованы вручную с целью уменьшения накладных
*    расходов на вызов (часть стандартного пролога и эпилога
*    закомментирована с демонстрационной целью ).
*
*    Накладные расходы: ближний call.
*
*    На самом деле это не С++ функция, а скорее подпрограмма ассемблера.
*
*    \note
*    Обработка двух тетрад за раз ( дублирующийся код ) производится исключительно
*    с целью уменьшения накладных расходов (можно было вынести отдельно).
*/
void __declspec( naked ) cvtByte2strhex( void )
{
    __asm 
    { 
                // ----------  prolog
                //push    ebp                ; Save ebp
                //mov     ebp, esp           ; Set stack frame pointer
                //sub     esp, __LOCAL_SIZE

                mov        ah,    al

                // ----------  обработка первого символа
                shr        ah,    4 

                cmp        ah,    10
                jb            less_then_10_1
            
                add        ah,    'A' - 10
                jmp        next_1

    less_then_10_1:
                or            ah,    '0'

    next_1:
                // ----------  обработка второго символа
                and        al, 0x0F                    // обнуление старшей тетрады

                cmp        al,    10
                jb            less_then_10_2
            
                add        al,    'A' - 10
                jmp        next_2

    less_then_10_2:
                or            al,    '0'
    next_2:

                // ----------  epilog

                //mov         esp, ebp      ; Restore stack pointer
                //pop         ebp           ; Restore ebp
                ret                       ; Return from function
    }
}


//! Конвертация заданного слова содержащего строково-шестнадцатиричное значение в двоичное значение.
/*!
*    \date        2005
*
*    \param[in,out]        ax        обрабатываемое слово
*
*    \retval    al        двоичное значение.
*
*    \warning
*    ЭТО НЕТРИВИАЛЬНАЯ ФУНКЦИЯ.
*
*    Пролог и эпилог реализованы вручную с целью уменьшения накладных
*    расходов на вызов (часть стандартного пролога и эпилога
*    закомментирована с демонстрационной целью )
*
*    Накладные расходы: ближний call
*
*    На самом деле это не С++ функция, а скорее подпрограмма ассемблера.
*
*    \note
*    Обработка слова ( дублирующийся код ) производится исключительно
*    с целью уменьшения накладных расходов (можно было вынести отдельно).
*/
void __declspec( naked ) cvtstrhexword2byte( void )
{
    __asm
    { 
            // ----------  prolog
            //push    ebp                ; Save ebp
            //mov     ebp, esp           ; Set stack frame pointer
            //sub     esp, __LOCAL_SIZE

            // ----------  обработка первого символа
            cmp        al,    '9'
            jbe        only_digits1
            
            and        al,    0xDF        // Принудительное преобразование в UpperCase
            sub        al,    7

    only_digits1:
            sub        al,    '0'
            shl        al,    4

            // ----------  обработка второго символа
            cmp        ah,    '9'
            jbe        only_digits2

            and        ah,    0xDF        // Принудительное преобразование в UpperCase
            sub        ah,    7

    only_digits2:
            sub        ah,    '0'

            // ----------  получить в AL - сконвертированное значение байта
            or            al,    ah

        // ----------  epilog

        //mov         esp, ebp      ; Restore stack pointer
        //pop         ebp           ; Restore ebp
        ret                       ; Return from function
    }
}

//! Преобразование числового значения в строково-шестнадцатиричное.
/*!
*    \date        2005
*
*    \param[in]        sourceVal            конвертируемое значение;
*    \param[in,ou]    pDest                    буфер принимающий сконвертированное значение;
*    \param[in]        sizeOfSourceVal    размер конвертируемого значения.
*
*    \return    pDest
*
*    Данная реализация поддерживает преобразование числовых значений следующих типов:
*        - char;
*        - short;
*        - long.
*
*    \note
*    Значение третьего аргумента (\e sizeOfSourceVal) выводится автоматически.
*    Это крайне необходимо, поскольку я не нашел другого способа получения размера \e T.
*
*    \sa
*    cvtFromStrHex2Value()
*/
template< typename T >
    char* cvtValue2StrHex( const T& sourceVal, char* pDest, const size_t sizeOfSourceVal = sizeof( T ) )
    {
        __asm
        {
                push        ecx
                push        edx
                push        esi

                // EDX - исходное значение
                mov        ecx,    DWORD PTR sourceVal
                mov        edx,    [ecx]

                // ECX - переменная цикла, равна кол-ву байт источника
                mov        ecx,    sizeOfSourceVal

                // ESI - адрес результата
                mov        esi,    pDest

    main_loop:

                mov        al,    dl

                call        cvtByte2strhex

                //    ----------
                shr        edx,    8

                // HACK: инструкция mov - не изменяет флаг ZF
                dec        cx

                // ----------  сохранение результатов
                mov        [esi + ecx * 2 + 1],    al
                mov        [esi + ecx * 2],    ah

                jnz        main_loop

                pop        esi
                pop        edx
                pop        ecx

                mov        eax,    pDest
        }
    }

//! Преобразование  строково-шестнадцатиричного значения в двоичное.
/*!
*    \date        2005
*
*    \param[in]            pSourse                буфер содержащий конвертируемое значение;
*    \param[in,out]        destVal                двоичное(сконвертированное) значение;
*    \param[in]            sizeOfDestVal        размер двоичного(сконвертированного) значения.
*
*    \return    destVal
*
*    Данная реализация поддерживает преобразование в значения следующих типов:
*        - char;
*        - short;
*        - long.
*
*    \note
*    Регистр символов - значения не имеет.
*
*    \warning
*    Функция не производит проверки на правильность значений:
*    в случае наличия в строке символа не принадлежащего
*    диапазону '0'-'9' && 'A'-'F' - последствия не определены.
*
*    \note
*    Значение третьего аргумента (\e sizeOfDestVal) выводится автоматически.
*    Это крайне необходимо, поскольку я не нашел другого способа получения размера \e T.
*
*    \sa
*    cvtValue2StrHex()
*/
template< typename T >
    T& cvtFromStrHex2Value( const char* pSourse, T& destVal, const size_t sizeOfDestVal = sizeof( T ) )
    {
        __asm
        {
                // Сохраняем регистры
                push        ecx
                push        edx
                push        esi

                // ECX - переменная цикла, равна кол-ву байт результата
                mov        ecx,    sizeOfDestVal

                // EDX - адрес результата
                mov        edx,    DWORD PTR destVal        

                // ESI - адрес обрабатываемого символа
                mov        esi,    pSourse
        main_loop:
                
                // ----------  сдвиг результата на 8 бит, в зависимости от типа результата
                cmp        sizeOfDestVal, 1
                jne        dest_not_char

                shl        BYTE PTR [edx], 8            // результат типа 'char'
                jmp        after_shift_dest

        dest_not_char:
                cmp        sizeOfDestVal, 2
                jne        dest_not_short

                shl        WORD PTR [edx], 8            // результат типа 'short'
                jmp        after_shift_dest

        dest_not_short:
                shl        DWORD PTR [edx], 8        // результат типа 'long'

        after_shift_dest:

                // ----------  загрузить в AX обрабатываемое слово
                mov        ax,    [ esi ]    
                add        si,    2

                call cvtstrhexword2byte

                // ----------  накопление результата
                or            BYTE PTR [edx],al

                loop        main_loop

                // Поместить в EAX destVal
                mov        eax, edx

                // Восстанавливаем регистры
                pop        esi
                pop        edx
                pop        ecx

        }
}

... << RSDN@Home 1.1.4 stable rev. 510>>

	От:	Кодт
	Дата:	17.04.04 17:31
	Оценка:

От:	orangy	http://twitter.com/orangy
Дата:	29.08.02 14:08
Оценка:	22 (2)

	От:	Кодт
	Дата:	29.08.02 09:37
	Оценка:	19 (2)

	От:	StDenis
	Дата:	13.07.05 13:55
	Оценка:	10 (1)

	От:	DK3981
	Дата:	13.07.05 14:59
	Оценка:	+1

От:	Flamer	http://users.livejournal.com/_flamer_/
Дата:	29.08.02 07:47
Оценка:

	От:	Анатолий
	Дата:	29.08.02 09:29
	Оценка:

От:	Lepsik	figvam.ca
Дата:	24.11.04 18:26
Оценка:

	От:	e-Xecutor
	Дата:	15.04.04 08:54
	Оценка:

	От:	MaximE
	Дата:	06.07.05 15:54
	Оценка:

	От:	srggal
	Дата:	20.07.05 20:42
	Оценка: