СПОСОБ КОДИРОВАНИЯ И ВЫЧИСЛЕНИЯ ДАТЫ С ИСПОЛЬЗОВАНИЕМ УПРОЩЕННОГО ФОРМАТА В ЦИФРОВЫХ УСТРОЙСТВАХ
DATE ENCODING AND COMPUTATION METHOD USING SIMPLIFIED FORMAT IN DIGITAL DEVICES

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к вычислительной технике и, в частности, к способам кодирования и преобразования даты для хранения и использования в цифровых устройствах: компьютерах, терминалах и пр.
Уровень техники
В цифровых устройствах для даты и времени используются внутренние форматы данных, которые отличаются от внешнего формата, т.е. от представления даты и времени в понятном для человека (пользователя) виде.
Это связано с тем, что принятых форматов (в разных странах), с одной стороны, много и, с другой стороны, все эти форматы избыточны с точки зрения объема хранимой информации. Для преобразования из внутреннего формата во внешний и наоборот требуется проведение ряда вычислений и проведение операций кодирования/декодирования.
В настоящее время известен ряд способов кодирования и преобразования даты и времени во внутренние форматы представления данных. Далее в описываемых технических решениях будут рассмотрены только способы, относящиеся непосредственно к датам, включающим год, месяц и день.
Так, известен способ кодирования и преобразования даты в программном обеспечении (ПО) SQL Server 2005 и SQL Server 2012 компании Microsoft [1, 2].
Для хранения даты и времени отводится два 4-байтовых целых числа (всего используется 8 байт). Первые 4 байта используются для хранения собственно даты и содержат количество дней до или после даты отсчета, в качестве которой выбрано 1 января 1900 года (для типа данных datetime; вторые 4 байта содержат текущее значение времени, представленного в виде трехсотых долей секунды, прошедших после полуночи).
Используется также хранение даты и времени с меньшей точностью. В этом варианте даты хранятся в виде 2-байтового целого числа, представляющего количество дней, прошедших с 1 января 1900 года (для типа данных smalldatetime; в двух следующих байтах хранится количество минут, прошедших после полуночи).
Таким образом, дата может храниться в виде целого числа и минимально занимать 2 байта (16 бит).
Для прямого преобразования даты по григорианскому календарю в целое число N может использоваться ряд последовательных преобразований и вычислений [3]
a(M-14)div 12,
y=Y+4800-a,
m=M+12*a-3,
J=D+(153*m+2) div 5+365*y+y div 4 - y div 100+y div 400-32075,
где a, y, m - промежуточные переменные целого типа;
M - месяц года, от 1 (январь) до 12 (декабрь);
D - день месяца, от 1 до 31;
Y - год григорианского календаря.
После этого для получения N из полученного значения J (номер юлианского дня для исходной даты) вычитают константу J0, которая зависит от стартовой даты и является номером юлианского дня для стартовой даты.
Однако для обратного преобразования целого числа N в дату используется еще большее количество преобразований и вычислений, сначала получают номер юлианского дня J, прибавляя константу J0, далее вычисляют
j=J+32044,
g=j div 146097,
dg=j mod 146097,
c=(dg div 36524+1)×3 div 4,
dc=dg-с×36524,
b=dc div 1461,
db=dc mod 1461,
a=(db div 365+1)×3 div 4,
da=db-a×365,
y=g×400+c×100+b×4+a,
m=(da×5+308)div 153-2,
d=da-(m+4)×153 div 5+122,
Y=y-4800+(m+2)div 12,
M=(m+2)mod 12+1,
D-d+1,
где b, с, d, j, g, da, db, dc, dg - промежуточные переменные целого типа.
В результате, несмотря на компактность хранения даты, известный способ содержит ряд сложных вычислений, учитывающих наличие високосных годов и способных занимать определенный ресурс вычислительной системы, что является недостатком известного способа.
Известен также способ кодирования и преобразования даты в ПО системы управления базами данных (СУБД) Oracle 7 компании Oracle [4].
Данные даты хранятся в фиксированных полях длиной 4 байта, соответствующих веку, году, месяцу, дню (еще 3 байта отведены для часа, минут и секунд). Соответственно, используемый способ позволяет хранить даты в диапазоне от 1 января 4712 года до н.э. до 31 декабря 4712 года нашей эры.
Номер юлианского дня позволяет датировать события от общей точки (эта точка принимается за 1 января 4712 г. до н.э. по юлианскому календарю). Для представления номера юлианского календаря используются целые числа. Метод, используемый в СУБД Oracle, представляет дату в виде семизначного числа (для наиболее часто используемых дат), так, например, 8 апреля 1991 года будет представлено в виде 2448355. Для преобразования даты во внутренний формат и наоборот используются специально созданные внутренние системные функции.
Такой метод позволяет упростить вычисления даты. Если значения байт принять N1, N2, N3, N4, тогда
D=N4,
M=N3,
Y=N1*100+N2.
Прямое преобразование даты в целое число N из 4 байт также несложно:
N1=Y div 100,
N2=Y mod 100,
N3=M,
N4=D.
Описанный способ принят за прототип.
Однако этот известный способ также имеет недостаток. Необходимость выделения для хранения каждой даты 4 байт приводит к очевидной избыточности и, как следствие, к ощутимому расходу памяти для хранения дат, что может быть неприемлемо для работы цифровых устройств, имеющих ограниченный ресурс памяти и производительности процессора.
Раскрытие изобретения
Техническим результатом является снижение необходимого объема памяти для хранения даты при сохранении простоты преобразований, свойственной прототипу.
Для этого предлагается способ, заключающийся в том, что
- выделяют для хранения данных о дате, включающей год, месяц и день, целое число длиной К бит;
- устанавливают для отсчета фиксированную дату как первое января определенного года Y0;
- вводят значения текущего года Y, месяца М, дня D;
- вычисляют целое число N для хранения данных о дате по формуле
N=D+(М-1)*32+(Y-Y0)*384.
Вычисление N по приведенной формуле означает, что:
- первые 5 бит двоичного представления числа N выделяют для дня месяца хранимой даты;
- оставшиеся К - 5 бит двоичного представления числа N выделяют для числа месяцев, прошедших после фиксированной даты. Затем сохраняют число N в двоичном формате. При необходимости обратного преобразования вычисляют дату по формулам
D=N mod 32,
M=(N div 32)mod 12+1,
Y=Y0+(N div 384),
где div - операция целочисленного деления (деления с отбрасыванием дробной части);
mod - операция взятия остатка от целочисленного деления.
В известных способах дата хранится в виде количества минимальных квантов изменения даты, т.е. дней, начиная с фиксированной даты, либо каждая компонента даты, то есть день месяца, месяц года и год, хранится в своем наборе бит, которые затем объединяются.
5
2
В предложенном способе оба этих подхода комбинируются: день месяца хранится в своем наборе бит, а оставшаяся часть данных хранится в виде числа месяцев - не минимальных квантов изменения даты, прошедших со стартовой даты. Очевидным эффектом предложенного способа является компактность представления - максимальное число дней в месяце (31 день) весьма близко к степени числа два (2=32), поэтому информационная избыточность предложенного способа хранения всего около 0,3 бита (log(12*32/365)). Поскольку информационная избыточность меньше одного бита, то для существенной части требуемых диапазонов дат требуемое число бит будет минимально возможным.
Сложность преобразований при этом оказывается такой же, как и для раздельного хранения компонент даты, т.е. минимальной.
Таким образом, минимально необходимый объем для хранения даты по предложенному способу снижается по сравнению с прототипом, при сохранении простоты вычислений и кодирования даты в число и обратно.
Можно показать преимущество предложенного способа на следующем примере.
Пусть требуется представление даты, покрывающее диапазон в 150 лет. Такой диапазон часто требуется в практических приложениях, где требуется представлять год рождения человека и обеспечить работоспособность выбранного представления минимум на 30 лет. Поэтому выберем начальную дату 01 января 1900 года (как в способе компании Microsoft) - требуем пригодность способа минимум до 2050 года.
11
Для предложенного способа потребуется 16 бит: 5 бит на представление дня месяца, остается 11 бит, что соответствует максимальному хранимому значению месяцев 2048(=2), что соответствует чуть более 169 годам. Таким образом, пригодность способа при стартовой дате 1 января 1900 года - до 2069 года.
В известном способе компании Oracle, принятом за прототип, для кодирования даты потребуется 4 байта (32 бита) - по байту на день месяца, месяц года, год столетия и столетие, что в 2 раза больше, чем в предложенном способе.
Даже если модифицировать этот способ, но все компоненты даты хранить в своих наборах бит - 5 на день месяца, 4 -  месяц года и оставшиеся биты для хранения года, для хранения года (не менее 150) потребуется не менее 8 бит:
7=
8
2128<150<2=256.
Итого в сумме получаем 17 бит, что на один бит хуже, чем в предлагаемом способе.
В известном способе компании Microsoft, в котором используется число дней, прошедших с фиксированной даты, потребуется представить не менее 150*365=54750 дней, на что потребуется не менее 16 бит:
15
16
2=32768<54750<2=65536.
Однако сложность и объем вычислений в способе компании Microsoft, как указано выше, значительно выше.
Предложенный способ может сократить объем хранимой информации, что будет особенно значимым в системах, обрабатывающих данные о датах и имеющих ограничения на объем памяти и ресурсы процессора или микроконтроллера.
Осуществление изобретения
Реализация предложенного способа может быть осуществлена в вычислительной системе, способной производить операции целочисленного деления, т.е. практически в любой, включая системы, работающие, например, под управлением операционной системы MS Windows.
Для реализации способа достаточно реализовать выполнение предложенных операций на каком-либо языке программирования.
Например, на языке C++ при использовании boost типов реализация может выглядеть следующим образом.
#include<boost/cstdint.hpp>
const int StartYear=1900; // В качестве стартовой даты берем 1 января 1900 г.
// Внутреннее представление даты
typedef boost::uint16_t InternalDate;
// Внешнее представление даты - отдельно год, месяц и день.
typedef struct {int year; int month; int day;} ExternalDate;
// Получаем внутреннее представления по внешнему
InternalDate PackDate (const ExternalDate & date)
{return date.day+(date.year-StartYear)·384+(date.month -1)*32;
}
// Получаем внешнее представление по внутреннему
void UnpackDate (InternalDate n, ExternalDate & date)
{date.year=StartYear+n/384;
date.month=(n/32)% 12+1;
date.day=n% 32;
}
Приведенная программная реализация операций не предусматривает проверку входных данные на правильность. Соответствующие операции проверки могут быть добавлены к конкретной реализации при необходимости.
Реализовать действия предложенного способа в составе программы или функции может специалист в области программирования (программист).
Наибольший эффект применение предложенного способа может дать в системах, обрабатывающих данные о датах и имеющих сильные ограничения на объем памяти и аппаратные ресурсы, а также передающие информацию о датах в условиях ограничения на объем передаваемой информации.
Примерами таких систем могут служить системы, хранящие и/или передающие различную информацию, в том числе и даты (например, даты рождения человека, дата отправки груза, дата отправления поезда и т.п.) в виде штрихкода. В этом случае каждый сэкономленный бит имеет значение. Часто с этим сопряжена задача обработки информации на микроконтроллерных устройствах. Простота кода в таких случаях немаловажна.
Источники информации
1. Дата и время (Transact-SQL), статья по адресу
http://msdn.microsoft.com/ru-ru/library/ms187819(v=sql.90)aspx.
2. Datetime (Transact-SQL), статья по адресу
http://msdn.microsoft.com/ru-ru/library/ms187819(у=sql.110). Aspx.
3. Julian day, статья по адресу
http://en.wikipedia.org/wiki/Julian_day.
4. Руководство разработчика приложений (Server Application Developer's Guide), 1992, перевод по адресу
http://www.interface.ru/fset.asp?Url=/oracle/ora7/ora7a03a.htm.