Баг Y292B: мы обречены (снова)

Измерение времени — очень сложная задача. Я выяснил это, набив шишки при попытке запрограммировать расширяемый хронометр для небесных тел Солнечной системы. Сложность в том, что все календарные системы имеют так много правил и исключений, что сборщик календаря, по сути, становится ещё одним языком программирования. Впрочем, мне хорошо знаком закон Завински*, поэтому я постарался избежать создания ещё одного Emacs.

^{*Закон Завински — выдуманный закон computer science, высмеивающий неизбежное разрастание фич. Он гласит, что каждая программа рано или поздно постарается прочитать электронную почту. Стоит отметить, что закон сформулирован в 90-х, поэтому и речь об электронной почте. Кстати, я нашёл хороший веб-сайт с другими законами computer science.}

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

Y2K, Y2038 и другие баги Y2xx — это на самом деле не совсем «баги», а простые переполнения выделенного пространства памяти. Unix и подобные ему компьютерные системы измеряют время, выполняя инкремент секунд в единой целочисленной переменной time_t. Естественно, такой хронометраж назван временем Unix, а 0 в нём означает полночь 1 января 1970 года.

В разных реализациях времени Unix для time_t используются разные типы данных. Когда тип данных достигает своего верхнего предела, он «сбрасывается» или до обратного (отрицательного) значения, или до нуля. В текущей основной ветви ядра Linux используются 64-битные числа со знаком. В таком решении точка сброса приходится на 292 277 026 596 год. Он настанет примерно через 292 миллиарда 277 миллионов 24 тысяч лет.

Но что потом?

Произойдёт переполнение и дата снова откатится назад на 278 миллиарда лет до Большого взрыва**? Без всяких сомнений, это нужно исправить. К счастью, на решение этой проблемы у нас есть 33 срока жизни нашего Солнца, но предлагать решения мы можем уже сегодня. Очевидным решением стало бы использование языка с динамической типизацией.

^{** В одном видео Нил Деграсс Тайсон говорит, что до Большого взрыва понятие времени было неактуально. Он предполагает, что до этой точки время как современная концепция могло и не существовать. Лично мне было очень интересно поразмыслить о времени в таком ключе.}

#!/usr/bin/perl
use strict;
use warnings;

my $time_f = 9223372036854775809; # за пределами long int
my $year_s = 31536000;            # секунд в году

while (1) {
   my $year = int($time_f / $year_s + 1970);
   print "unix time: $time_f \tyear: $year\n";
   $time_f++;
   #sleep(1);
}

Проблема решена (ярые фанаты скобок могут решить её на Lisp). Теперь значение переменной может увеличиваться неограниченно, единственным ограничением станет объём физической памяти. Значение time_f (f означает fix) может состоять из чуть более 1 миллиарда разрядов на 1 ГБ памяти. Однако Линус Торвальдс лучше будет работать в Debian, чем писать код не на C, так что если мы хотим, чтобы это изменение попало в ядро, нужно использовать что-то более статическое.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>    // GNU Multiple Precision Arithmetic Library

int main() {

   mpz_t time_f, year_s, year;
   mpz_init(time_f);
   mpz_init(year_s);
   mpz_init(year);

   mpz_set_str(time_f, "9223372036854775809", 10); // за пределами long int
   mpz_set_str(year_s, "31536000", 10);            // секунд в году

       while (1) {
       mpz_tdiv_q(year, time_f, year_s);

       gmp_printf("unix time: %Zd", time_f);
       gmp_printf("\t\tyear: %Zd\n", year);

       // Инкремент времени unix на 1
       mpz_add_ui(time_f, time_f, 1);

   }
   return 0;
}

В C можно использовать GNU Multiple Precision Arithmetic Library, которая позволит нам динамически распределять память под переменные. К сожалению, gmp.h несовместима с пространством ядра, так что нам придётся проектировать эту ересь с нуля.

Для динамического распределения памяти на C можно использовать массивы. Тогда при помощи строк мы сможем читать числа гораздо больше long long int точно так же, как это делается при помощи gmp.h. Было бы здорово ещё создать функцию деления для преобразования секунд в удобные единицы времени, например в годы.

Пусть структура BigInt описывает большие целые числа с произвольной точностью при помощи массива разрядов.

typedef struct {
   int *digits; // Указатель на массив разрядов
   int size;    // Количество разрядов
} BigInt;

Далее нам нужно инициализировать BigInt из строкового ввода.

BigInt initBigInt(const char *str) {
   int len = strlen(str);  // Получаем длину строки
   BigInt num;             // Объявляем переменную BigInt
   num.size = len;         // Присваиваем BigInt размер, равный длине строки
   num.digits = (int *)malloc(len * sizeof(int)); // Распределяем память под разряды
   for (int i = 0; i < len; i++) {
       num.digits[i] = str[len - 1 - i] - '0';    // Преобразуем разряды в int и сохраняем их в обратном порядке
   }
   return num;             // Возвращаем инициализированный BigInt
}

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

void freeBigInt(BigInt *num) {
   free(num->digits);
   num->digits = NULL;
   num->size = 0;
}

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

int main() {
   BigInt time_f = loadCurrentUnixTime();
   BigInt year_s = initBigInt("31536000"); // Секунд в году

...

Теперь нам нужно заняться делением в столбик. Эта часть была для меня довольно проблематичной по двум причинам. C — не самый мой любимый язык*** и, как выяснилось, деление столбиком в разных странах преподают по-разному. Похоже, я изучал германо-евразийский способ, который немного отличается от способа, преподаваемого в англоговорящих странах. (Получается, математика — не такой уж универсальный язык...)

^{*** Хоть я и ценю скорость и непосредственный контроль за кодом, мне всё равно хочется писать чуть более интуитивно понятный код. Но ввиду того, что под этим я подразумеваю Perl, наверно, всё сводится к личным предпочтениям.}

Как бы то ни было, благодаря моим записям из младшей школы и одной книге по C из местной библиотеки я смог создать такую функцию деления:

void divideBigInt(BigInt *dividend, BigInt *divisor, BigInt *result) {
   // Инициализируем размер результата и распределяем памятью под его разряды
   result->size = dividend->size;
   result->digits = (int *)calloc(result->size, sizeof(int));

   // Инициализируем вспомогательный BigInt с именем current
   BigInt current;
   current.size = 0;
   current.digits = (int *)calloc(dividend->size, sizeof(int));

   // Заполняем вспомогательную переменную "current"
   for (int i = dividend->size - 1; i >= 0; i--) {
      // Сдвигаем разряды в "current" влево
      for (int j = current.size; j > 0; j--) {
         current.digits[j] = current.digits[j - 1];
      }
      // Добавляем следующий разряд из делимого к "current"
      current.digits[0] = dividend->digits[i];
      current.size++;

      // Удаляем начальные нули в "current"
      while (current.size > 1 && current.digits[current.size - 1] == 0) {
         current.size--;
      }

      int count = 0;
      // Выполняем деление, пока "current" не окажется меньше делителя
      while (isGreaterOrEqual(&current, divisor)) {
      BigInt tempResult;
      // Вычитаем делитель из "current"
      subtractBigInt(&current, divisor, &tempResult);
      free(current.digits);
      current = tempResult;
      count++;
      }

      // Сохраняем знаменатель в результат
      result->digits[i] = count;
   }

   // Удаляем начальные нули из результата
   while (result->size > 1 && result->digits[result->size - 1] == 0) {
       result->size--;
   }

   free(current.digits);
}

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

Следующим логичным шагом было бы модифицировать код так, чтобы его можно было встроить в time.c ядра Linux, однако мои знания программирования в пространстве ядра стремятся к нулю. Кроме того, я не знаю, как функция деления будет справляться с простыми числами больше long long int.

Тем не менее, fixed.c опубликован под лицензией GPLv3 и доступен для скачивания всеми, кто хочет устранить проблему Y292b на уровне ядра для будущих поколений. Удачи, и помните — часики тикают.