Определить, являются ли буквы набора символов выполнения смежными

В коде переключатель используется для преобразования букв в непрерывные значения. Оптимизирующие компиляторы в целом не справятся с этой задачей, а также простое условие непрерывной цифры прямо перед переключением. Как я могу определить, какой набор символов выполнения используется, и/или сделать вывод, что буквы являются смежными, чтобы заменить его простыми условными выражениями?

static long digit_value(char c)
{
    if (c >= '0' && c <= '9')
        return (c-'0');

    switch(c) {
    case 'a':
    case 'A':
        return 10;
    case 'b':
    case 'B':
        return 11;
    case 'c':
    case 'C':
        return 12;
    case 'd':
    case 'D':
        return 13;
    case 'e':
    case 'E':
        return 14;
    case 'f':
    case 'F':
        return 15;
    case 'g':
    case 'G':
        return 16;
    case 'h':
    case 'H':
        return 17;
    case 'i':
    case 'I':
        return 18;
    case 'j':
    case 'J':
        return 19;
    case 'k':
    case 'K':
        return 20;
    case 'l':
    case 'L':
        return 21;
    case 'm':
    case 'M':
        return 22;
    case 'n':
    case 'N':
        return 23;
    case 'o':
    case 'O':
        return 24;
    case 'p':
    case 'P':
        return 25;
    case 'q':
    case 'Q':
        return 26;
    case 'r':
    case 'R':
        return 27;
    case 's':
    case 'S':
        return 28;
    case 't':
    case 'T':
        return 29;
    case 'u':
    case 'U':
        return 30;
    case 'v':
    case 'V':
        return 31;
    case 'w':
    case 'W':
        return 32;
    case 'x':
    case 'X':
        return 33;
    case 'y':
    case 'Y':
        return 34;
    case 'z':
    case 'Z':
        return 35;
    default:
        break;
    }

    return -1;
}

c character-encoding ascii ebcdic
person hdante    schedule 20.07.2020    source источник
comment
Связанный/контекст: stackoverflow.com/questions/13141776/   -  person mkrieger1    schedule 21.07.2020
comment
Несмотря на то, что язык не требует этого, если вам не нужна переносимость в среду EBCDIC, вы можете рассчитывать на то, что буквы будут последовательными.   -  person Barmar    schedule 21.07.2020
comment
Достаточно ли просто исключить EBCDIC? (это для меня какая-то легенда, так как я никогда не работал с такой кодировкой).   -  person Roberto Caboni    schedule 21.07.2020
comment
Наборы символов могут иметь пробелы, но AFAIR их необходимо отсортировать. Разве проверка 'z'-'a'==25 не помогла бы обнаружить пробелы?   -  person Gerhardh    schedule 21.07.2020

Ответы (4)


arrow_upward
7
arrow_downward

Как я могу определить, какой набор символов выполнения используется, и/или сделать вывод, что буквы следуют друг за другом?

Во время компиляции просто протестируйте их все. ('a-z' опущены для простоты)

static_assert(
  'A' == ('B' - 1) &&
  'B' == ('C' - 1) && 'C' == ('D' - 1) && 'D' == ('E' - 1) && 'E' == ('F' - 1) && 'F' == ('G' - 1) && 'G' == ('H' - 1) && 'H' == ('I' - 1) && 'I' == ('J' - 1) && 'J' == ('K' - 1) && 'K' == ('L' - 1) && 'L' == ('M' - 1) && 'M' == ('N' - 1) && 'N' == ('O' - 1) && 'O' == ('P' - 1) && 'P' == ('Q' - 1) && 'Q' == ('R' - 1) && 'R' == ('S' - 1) && 'S' == ('T' - 1) && 'T' == ('U' - 1) && 'U' == ('V' - 1) && 'V' == ('W' - 1) && 'W' == ('X' - 1) && 'X' == ('Y' - 1) &&
  'Y' == ('Z' - 1), "Dinosaur: not continuous A-Z");

static int digit_value(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
  return -1;
}

Другие тесты динозавров.

Или используйте медленный, но очень портативный:

static int digit_value(char c) {
  static const char *base36 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  const char *p = strchr(base36, (unsigned char) c);
  if (p && *p) {
    return (int) (p - base36);
  }
  return -1;
}

Или, может быть, большой #if?

#if ('A' == ('B' - 1) && 'B' == ('C' - 1) && 'C' == ('D' - 1) && 'D' == ('E' - 1) && 'E' == ('F' - 1) && 'F' == ('G' - 1) && 'G' == ('H' - 1) && 'H' == ('I' - 1) && 'I' == ('J' - 1) && 'J' == ('K' - 1) && 'K' == ('L' - 1) && 'L' == ('M' - 1) && 'M' == ('N' - 1) && 'N' == ('O' - 1) && 'O' == ('P' - 1) && 'P' == ('Q' - 1) && 'Q' == ('R' - 1) && 'R' == ('S' - 1) && 'S' == ('T' - 1) && 'T' == ('U' - 1) && 'U' == ('V' - 1) && 'V' == ('W' - 1) && 'W' == ('X' - 1) && 'X' == ('Y' - 1) && 'Y' == ('Z' - 1))

static int digit_value(char c) {
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
  return -1;
}

#else

static int digit_value(char c) {
  static const char *base36 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  const char *p = strchr(base36, (unsigned char) c);
  if (p && *p) {
    return (int) (p - base36);
  }
  return -1;
}

#endif

Или .... если UCHAR_MAX не слишком большой и беспокоит скорость, сделайте таблицу поиска и пропустите последовательные проблемы.

#include <limits.h>
int digit_value(char c) {
  unsigned char val[UCHAR_MAX] = {['0'] = 1, ['1'] = 2, ['2'] = 3, ['3'] = 4,
      ['4'] = 5, ['5'] = 6, ['6'] = 7, ['7'] = 8, ['9'] = 10, 
      ['A'] = 11, ['B'] = 12, ['C'] = 13, ['D'] = 14, ['E'] = 15, ...
      ['a'] = 11, ['b'] = 12, ['c'] = 13, ['d'] = 14, ['e'] = 15, ...
  };
  return val[(unsigned char) c] - 1;
}
person chux - Reinstate Monica    schedule 20.07.2020
comment
Код должен разрешать любой набор символов, но static_assert запрещает несмежные. - person hdante; 21.07.2020
comment
@hdante Просто используйте if ('A' == ('B' - 1) && 'B' == ('C' - 1) ... 'Y' == ('Z' - 1)) и 1-й digit_value(), иначе используйте 2-й digit_value(char c) с его strchr(). Компиляция будет оптимизирована. - person chux - Reinstate Monica; 21.07.2020
comment
@chux-ReinstateМоника милая, не знаю, радоваться мне или грустить, но я попробую - person hdante; 21.07.2020
comment
@EricPostpischil Правда 'B' == 'A'+1 может быть яснее. Педантическая озабоченность: учитывая, что A-Z не может быть нулевым символом, 'A' == 'B'-1 не может переполняться (буквы набора символов выполнения положительные), тем не менее, теоретически, some_letter+1 может intmax_t переполняться. И мы делаем код для обнаружения странных реализаций. - person chux - Reinstate Monica; 21.07.2020
comment
Единственное, что меня беспокоит, как я уже писал в своем ответе, это то, что static_assert assert — это новая функция стандарта, и она вряд ли будет поддерживаться в старой системе. - person Roberto Caboni; 21.07.2020
comment
@RobertoCaboni Для C99 легко существуют альтернативы: Есть ли замена static_assert, которая удовлетворяет стандарту C99? Обычно для эмуляции при сбое to для массива размером -1. - person chux - Reinstate Monica; 21.07.2020
comment
@chux, это была просто побочная проблема. В любом случае, цепочка `#if` тоже сработает. - person Roberto Caboni; 21.07.2020

arrow_upward
1
arrow_downward

Вы можете написать соответствующий тест для условной компиляции, как ответил @chux. Однако, если вам нужно поддерживать наборы символов с несмежными буквами, вам нужна реализация, которая поддерживает это, и поиск в таблице будет намного эффективнее, чем то, что вы представляете в вопросе. Настолько больше, что вы можете использовать его для всех случаев вместо поддержки двух отдельных реализаций. Например:

static long digit_value(char c) {
    static const long dvs[UCHAR_MAX + 1] = {
      [0] = 1, [1] = 2, [2] = 3, [3] = 4, [5] = 6, [7] = 8, [8] = 9, [9] = 10,
      ['A'] = 11, ['B'] = 12, ['C'] = 13, ['D'] = 14, ['E'] = 15, ['F'] = 16, ['G'] = 17,
      ['H'] = 18, ['I'] = 19, ['J'] = 20, ['K'] = 21, ['L'] = 22, ['M'] = 23, ['N'] = 24,
      ['O'] = 25, ['P'] = 26, ['Q'] = 27, ['R'] = 28, ['S'] = 29, ['T'] = 30, ['U'] = 31,
      ['V'] = 32, ['W'] = 33, ['X'] = 34, ['Y'] = 35, ['Z'] = 36,
      ['a'] = 11, ['b'] = 12, ['c'] = 13, ['d'] = 14, ['e'] = 15, ['f'] = 16, ['g'] = 17,
      ['h'] = 18, ['i'] = 19, ['j'] = 20, ['k'] = 21, ['l'] = 22, ['m'] = 23, ['n'] = 24,
      ['o'] = 25, ['p'] = 26, ['q'] = 27, ['r'] = 28, ['s'] = 29, ['t'] = 30, ['u'] = 31,
      ['v'] = 32, ['w'] = 33, ['x'] = 34, ['y'] = 35, ['z'] = 36
    };

    return dvs[(unsigned char) c] - 1;
}

Обратите внимание, что символы в базовом наборе символов выполнения, который включает в себя все десятичные цифры и прописные и строчные буквы латинского алфавита, гарантированно имеют неотрицательные целые значения. Это несколько упрощает инициализатор таблицы. Также обратите внимание, что элементы, которые не инициализированы явно, будут по умолчанию инициализированы нулем, который в конечном итоге преобразуется в возвращаемое значение -1 путем вычитания 1 из табличного значения.

person John Bollinger    schedule 20.07.2020
comment
Может быть, с long dvs[] по char dvs[]? - person chux - Reinstate Monica; 21.07.2020
comment
Возможно, @chux. Я просто сопоставил тип элемента таблицы с типом возвращаемого значения (который, в свою очередь, я взял из кода OP), зная, что таблица будет занимать больше места, чем нужно. Я не уверен в влиянии на производительность выбора типа элемента таблицы в целевых средах OP, но возможно, что изменение его на char обеспечит как преимущество в размере, так и преимущество в скорости. - person John Bollinger; 21.07.2020

arrow_upward
0
arrow_downward

Чтобы быть переносимым и наиболее эффективным, используйте таблицу поиска

const char table[128] = {
                         ['0'] = 0,  ['1'] = 1, /* ... */ ['9'] = 9, 
                         ['a'] = 10, ['A'] = 10,
                         ['b'] = 11, ['B'] = 11,
                         ['c'] = 12, ['C'] = 12,
                         ['d'] = 13, ['D'] = 13,
                         ['e'] = 14, ['E'] = 14,
                         ['f'] = 15, ['f'] = 15,
                         ['g'] = 16, ['g'] = 16,
                         ['h'] = 17, ['H'] = 17,
                         ['i'] = 18, ['I'] = 18,
                         ['j'] = 19, ['J'] = 19,
                         /* etc etc */
};

int get_value(char ch)
{
    return table[ch & 0x7f];
}

и сгенерированный код:

get_value:
        movsx   rdi, dil
        movsx   eax, BYTE PTR table[rdi]
        ret
person 0___________    schedule 20.07.2020
comment
Опечатки в ['i'] = 18, ['J'] = 18, и других. Предложите table[256] или подобное и защиту от отрицательного индекса в return table[ch]; - person chux - Reinstate Monica; 21.07.2020

arrow_upward
0
arrow_downward

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

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

Я бы выполнил проверку с помощью общих директив препроцессора, то есть с цепочкой #if, каждая из которых гарантирует, что представление одного символа является смежным с представлением предыдущего символа.

Простая проверка во время выполнения

Проверка времени компиляции была хорошо освещена в других ответах, поэтому я просто хочу предложить простой способ времени выполнения для исключения кодировки EBCDIC: предположение - это сценарий в котором кодировка может быть либо EBCDIC, либо ASCII.

Таким образом, исключая EBCDIC, мы можем предположить, что используется кодировка ASCII, поэтому символы идут непрерывно.

Необходимо учитывать только две простые функции EBCDIC:

  • Буквы, которые имеют несмежные десятичные представления, хорошо известны (например, 'j' != 'i'+1)
  • Алфавитные символы должны иметь общие десятичные представления во всех сотнях вариантов EBCDIC, как рекомендовано на этой странице IBM: неизменяемый набор символов

So:

static long digit_value(char c)
{
    if (c >= '0' && c <= '9')
        return (c-'0');

    if ( 'j' == 'i'+1 ) //if it's not EBCDIC 
    {
        if( c >= 'a' && c <= 'z' )
        {
             return 10 + c - 'a';
        }
        else if ( c >= 'A' && c <= 'Z' )
        {
            return 10 + c - 'A';
        }
    }

    return -1;
}

Код ошибки возвращается в случае кодировки EBCDIC, а в случае кодировки ASCII простое условие гарантирует, что диапазон [10 - 35] возвращается как для символов нижнего, так и для верхнего регистра.

person Roberto Caboni    schedule 20.07.2020