1. Си / Говнокод #23275

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    94. 94
    95. 95
    96. 96
    97. 97
    static inline void set0b (const uint8_t at, uint64_t bm[static 4])
    {
      bm[at / 64] &= ~(1ULL << (at % 64));
    }
    
    static inline  void set1b (const uint8_t at, uint64_t bm[static 4])
    {
      bm[at / 64] |= 1ULL << (at % 64);
    }
    
    static inline void inv_b (const uint8_t at, uint64_t bm[static 4])
    {
      bm[at / 64] ^= 1ULL << (at % 64);
    }
    
    
    static inline uint8_t find_empt_pos (const uint64_t bm[static 4])
    {
      if (bm[0] != UINT64_MAX)
      {
        return __builtin_ctzll(~bm[0]) + 64 * 0;  // __builtin_ctzll - https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
      }
      if (bm[1] != UINT64_MAX)
      {
        return __builtin_ctzll(~bm[1]) + 64 * 1;
      }
      if (bm[2] != UINT64_MAX)
      {
        return __builtin_ctzll(~bm[2]) + 64 * 2;
      }
      if (bm[3] != UINT64_MAX)
      {
        return __builtin_ctzll(~bm[3]) + 64 * 3;
      }
      fprintf(stderr, "ERROR! No empty space!\n");
      exit (-1);
    }
    
    static inline uint8_t allocate_ll (uint64_t bm[static 4])
    {
      uint8_t tmp = find_empt_pos (bm);
      set1b (tmp, bm);
      return tmp;
    }
    
    static inline void inject(const uint8_t prev_p, const uint8_t next_p, const uint8_t at, struct ll_data a[static 256])
    {
      a[next_p].ll.prev = at;
      a[prev_p].ll.next = at;
    
      a[at].ll.prev = prev_p;
      a[at].ll.next = next_p;
    }
    
    static inline void remove_betw(const uint8_t prev_p, const uint8_t next_p, struct ll_data a[static 256])
    {
      a[prev_p].ll.next = next_p;
      a[next_p].ll.prev = prev_p;
    }
    
    static inline void remove_at(const uint8_t at, struct ll_data a[static 256], uint64_t bm[static 4])
    {
      uint8_t prev_t = a[at].ll.prev;
      uint8_t next_t = a[at].ll.next;
    
      set0b (at, bm);
    
      a[at].ll.prev = next_t;
      a[at].ll.next = prev_t;
    }
    
    
    void add_elem_next (struct ll_all *a, const uint8_t elm, const int value)
    {
      uint8_t pos = allocate_ll (a->bm);
      inject(elm, a->arr[elm].ll.next, pos, a->arr);
      set_elm (pos, value, a->arr);
    }
    
    void add_elem_prev (struct ll_all *a, const uint8_t elm, const int value)
    {
      uint8_t pos = allocate_ll (a->bm);
      inject(a->arr[elm].ll.prev, elm, pos, a->arr);
      a->arr[pos].data = value;
    }
    
    void rem_elem_next (struct ll_all *a, const uint8_t elm)
    {
      set0b (a->arr[elm].ll.next, a->bm);
      remove_betw (elm, a->arr[a->arr[elm].ll.next].ll.next, a->arr);
    }
    
    void rem_elem_prev (struct ll_all *a, const uint8_t elm)
    {
      set0b (a->arr[elm].ll.next, a->bm);
      remove_betw (a->arr[a->arr[elm].ll.prev].ll.prev, elm, a->arr);
    }

    Тру-царская неанскилльная реализация двусвязного списка внутри массива.
    К сожалению, весь код не помещается, см https://wandbox.org/permlink/Ky8fnuqyE0Ahxftm

    Запостил: j123123, 18 Августа 2017

    Комментарии (37) RSS

    • > struct ll_data a[static 256]

      это че за такой загадочный `static`?
      Ответить
      • Это C99.

        Array declarators as function arguments now have a meaningful difference from pointer declarators: you can put in type qualifiers. Of particular interest is the very odd optimizer hint of giving an array declarator the static type modifier. Given this declaration: int foo(int a[static 10]);

        It is undefined behavior to call foo() with a pointer that doesn't point to at least 10 objects of type int. This is an optimizer hint. All you're doing is promising the compiler that the argument passed to the function will be at least that large; some machines might use this for loop unrolling.
        Ответить
      • А теперь внимание (барабанная дробь)! Посмотрим реализацию в гэцэцэ:

        The information provided by static in parameter array declarators is not used for optimization. It might make sense to use it in future in conjunction with work on prefetching.

        Гэцэцэ тупо игнорирует это слово, обещая, что когда-нибудь в будущем (через 100500 версий) это слово будет влиять на оптимизацию.
        Ответить
        • это намек что анроллеру это по барабану.

          с другой стороны, префетч когда он был мне нужен в либо в компайлерах глючил - либо в процах глючил (сегфолты или доп тормоза). я ему как то не сильно доверяю.
          Ответить
        • В clang это слово влияет на то, что компилятор будет в некоторых случаях плеваться ворнингами https://wandbox.org/permlink/W3kCc7Bl7xCC7dae
          Ответить
      • http://govnokod.ru/19996
        Ответить
        • Самое интересное, что Dummy00001 заглядывал в тот говнокод, но... ничего не запомнил. Да и мне пришлось гуглить с нуля.

          Вот такой у сишечки интуитивно понятный и запоминаемый синтаксис...
          Ответить
          • > Самое интересное, что Dummy00001 заглядывал в тот говнокод, но... ничего не запомнил.

            да я просто тормоз. может с третьего раза запомню.
            Ответить
          • хз, лично я сразу запомнил
            Ответить
            • если тебе этот синтакс нужен - то да. но я не фанат анроллов.

              программирование на темплейтах и констэкспр решают меня косающиеся проблемы - там я даже сильно и не пытался запомнить (и реально даже не нужно т.к. ни один проект даже не с++11) но мозги сами по себе впитали. а синтакс там еще хуже.
              Ответить
            • память хорошиая?
              Ответить
    • И что тут интересного? Типичная практика для языков, в которых нет указателей. Ну или когда очень хочется сэкономить на размерах указателей. И да, на C++ это можно сделать универсальнее:
      1) в нодах можно хранить не только int
      2) размер указателя можно вычислять в компайл-тайме из размера пула
      Ответить
      • В Си я могу сделать кодогенератор, и это будет настолько же универсально
        Ответить
        • > В Си я могу сделать кодогенератор
          Мы все видели, что ты можешь. Память только не забудь правильно почистить. А потом попробуй оформить свой генератор в реюзабельную библиотеку.
          Ответить
          • > Память только не забудь правильно почистить.

            Я могу и напитон перейти, если память будет лень чистить. Вообще, в компилтайм-метушне на шаблонах нигде память не чистится вообще никак (ни руками, ни через GC) и при этом никого это особо не волнует, почему я об этом думать должен? Так что можно просто смело срать в память, а потом пусть оно само чистится операционкой после завершения процесса кодогенерации.
            Ответить
            • Я как человек, который работал в команде, где активно использовалась кодогенерация на питоне (причём я предложил использовать кодогенерацию, но не питон), торжественно заявляю: кодогенерация сложных вещей внешними инструментами это такой геммор, что лучше держаться от неё подальше как можно дольше. У нас практически не было выбора, уж больно много бойлерплейта было, а компайл-тайм рефлексию в плюсцы не завезли. В Common Lisp бы эта кодогенерация осталась внутри языка и получилась бы красивой, но вся остальная программа, наверное, превратилась бы говно :)
              Ответить
              • Кстати, слышал про кодогенератор(DSL) на хаскеле - Copilot https://hackage.haskell.org/package/copilot ?
                Ответить
              • кодогенерация не панацея, и важно сразу разделять что делается в кодгене, что делается на языке. потому что без разделения, будут проблемы/решения постоянно пихатся туда-сюда, и только хаос будет множится.

                самые успешние кодогены которые я писал, они все были одно-целевые.

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

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

                ЗЫ а лисп сюда припихивать просто не правомерно. с убогим препроцессором ц/крестов, сравнинивать с лиспом просто нечестно.
                Ответить
                • Я вот кстати пытался сделать альтернативный лиспосинтаксис для Си когда-то, сначала код на Си, потом короткое пояснение, потом то, как бы это в s-expr выглядело:

                  int max (int a, int b)
                  {
                    int out;
                    if(x > y)
                    {
                      out = x;
                    }
                    else
                    {
                      out = y;
                    }
                    return out;
                  }
                  
                  int main (int argc, char **argv)
                  {
                    int x, y, out;
                    printf ("enter val x y\n");
                    scanf("%i %i", &x, &y);
                    out = max(x, y);
                    printf ("max: %i\n", out);
                    return 0;
                  }
                  -------------------------
                   
                  (funcname) ({0}) ({1}) ({2})
                  (
                    {3} код функции
                  )
                  {0}передача по значению, только для чтения
                  {1}только для записи, передача по ссылке, первый аргумент отсюда возвращается так, как если return в си.
                  {2}чтение-запись, передача по ссылке
                  
                  
                  ite это не функция, это макрос такой, который разворачивается в конструкцию из goto:
                    (ite (> x y)
                    (
                      (= out x)
                      (= out y)
                    ))
                  получаем:
                  
                  (
                    (stackvar (type ptr (TrueLabel FalseLabel EndLabel)))
                    (GOTOIF E(not E(> x y)) FalseLabel)
                    (= out x)
                    (GOTO EndLabel)
                    (##FalseLabel)
                    (= out y)
                    (##EndLabel)
                  )
                  
                  -----------------------
                  (deffun
                  ((max) (type int (x y)) ((type int out)) ()
                  (
                    (ite (> x y)
                    (
                      (= out x)
                      (= out y)
                    ))
                    (ret)
                  ))
                  
                  
                  (deffun
                  ((main) ((type int argc) (type (ptrto(ptrto char)) argv) ) ((type int out)) ()
                  (
                    (stackvar (type int (x y out)))  
                    (print "enter val x y\n")
                    (scanf () (NULL x y))
                    
                    // этим мы обозначаем, что мы не присваиваем в out список (max x y)
                    // А присваиваем в out результат вызова ф-ции max с аргументами x, y.
                    // то же самое можно было бы записать так: (max x y out)
                    (=  out E(max x y))
                  
                    (print ("max:" out "\n"))
                    (= out 0)
                    (ret)
                  ))
                  Ответить
                  • хм. интересно.

                    в смысле - интересно сколько минут понадобится про-лисперу что бы написать интерпретатор ц?

                    ЗЫ гото?.. почитай книжки по компиляции - ты похоже пытаешь переизобрести BBs (basic blocks).
                    Ответить
                  • я бы первым шагом просто поменял синтакс. `a = b;` -> `(assign a b)`, `func1(a ,b);` -> `(func1 a b)`.

                    ... хм. вспоминаю что сам подобным мозги себе разминал. остановился на том что лиспа сильно не знаю, и вещи типа указателей (передача по ссылке/по значению) сложно переносить (потому что их в лиспе в принципе нет).
                    Ответить
                  • > (= out y)

                    Сразу видно, что ты на лиспе не пишешь, а гомоиконы в суе поминаешь. Лисперу бы такой синтаксис для присваивания точно бы в голову не пришёл. Потому что во всех лиспах это проверка на равенство (чисел).
                    Ответить
                    • > Потому что во всех лиспах это проверка на равенство (чисел).

                      Но поскольку я пытаюсь сишку сделать лиспом, проверка равенства у меня будет ==
                      Ответить
                      • Но зачем делать сишку лиспом? В CL, насколько я знаю, и так можно императивщиной обмазаться по самое не хочу.
                        Ответить
                        • только там GC и жирный рантайм
                          Ответить
                          • А как ты будешь без жирного рантайма и GC гомоиконить? Ручками память под AST выделять? Вот у Haskell более тонкий рантайм (нет eval, в частности), чем у CL, из-за этого TH -- то ещё удовольствие. Умножь его ещё на 20.
                            Ответить
                            • Для компилтайм-метушни можно и GC с жирным рантаймом поиспользовать, а когда все окончательно скомпилируется, можно и без GC сделать результат, чтоб в контроллер впихнуть.

                              Да и вот eval в контроллер же фиг впихнешь, раз там архитектура гарвардская. Разве что на шитом коде делать, но это для анскиллябр, к тому же много флеша отхавает
                              Ответить
                              • Гомоиконы без eval -- это как-то тоскливо и бессмысленно. А для того юзкейза, который ты описал, они вообще не нужны.
                                Знаю кучу людей (включая себя любимую), которые которые кудовские ядра генерят напитоне, схемке и прочих абсолютно анскилльных языках.
                                В haskell целые language-c и language-c-quote есть.
                                Ответить
                                • Ты же архитектор. Зачем ты генеришь кудовские ядра?
                                  Ответить
                                  • https://comfy.moe/ywztly.jpeg
                                    (Это было на другой работе)
                                    Ответить
                          • > только там GC и жирный рантайм

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

                            Тут главное как-то провести грань между компайлтаймом и рантаймом. И GC в компайлтайме -- это офигенно удобно. А в рантайме выжившие данные станут какими-нибудь массивами констант.
                            Ответить
                            • > И что? Ты же будешь гомоиконить на хосте, а на контроллер пихать уже готовый результат, параметризованный под конкретную задачу.

                              Да, я про это еще в 2017 году написал, посмотри выше мой комментарий.

                              > j123123 18.08.2017 16:02 # 0
                              > Для компилтайм-метушни можно и GC с жирным рантаймом поиспользовать, а когда все окончательно скомпилируется, можно и без GC сделать результат, чтоб в контроллер впихнуть.
                              Ответить
                  • > пытался сделать альтернативный лиспосинтаксис для Си
                    https://github.com/kiselgra/c-mera
                    Ответить

    Добавить комментарий