УСКОРЕНИЕ ХЭШИРОВАНИЯ РАСТРОВОГО ПРЕДСТАВЛЕНИЯ RDP С ИСПОЛЬЗОВАНИЕМ ИНСТРУКЦИЙ SIMD Российский патент 2015 года по МПК G06F17/00 H04L12/743 

Предшествующий уровень техники

Хотя раньше компьютеры были изолированы и имели минимальное или ограниченное взаимодействие с другими компьютерами, сегодня компьютеры взаимодействуют с широким спектром других компьютеров через сети связи, такие как локальные сети и глобальные сети. С распространением сети INTERNET™ соединения между компьютерами получили большую важность, и было раскрыто множество новых приложений и технологий. Рост широкомасштабных сетей и широкая доступность дешевых персональных компьютеров в корне изменили то, как многие люди работают, взаимодействуют, осуществляют связь и играют.

Одна из форм сетевой связи, которая получает все большую популярность, в целом обозначается как виртуальные вычислительные системы, которые могут использовать такие протоколы, как Протокол Удаленного Рабочего Стола (Remote Desktop Protocol, RDP), Архитектура Независимых Вычислений (Independent Computing Architecture, ICA) и другие, чтобы разделять рабочий стол и другие приложения с удаленным клиентом. Такие вычислительные системы, как правило, передают нажатия клавиатуры и вводы или щелчки мыши из клиента в сервер, а обновления экрана передаются в обратном направлении через сетевое соединение (например, INTERNET). По существу, для пользователя его машина работает как часть локальной сети, тогда как в реальности клиентское устройство только передает экранные снимки приложений, когда они появляются на стороне сервера.

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

Для смягчения этих проблем кадр (фрейм), который передается клиенту (такой как окно приложения), может быть разделен на мозаичные элементы. Эти мозаичные элементы, далее, кэшируются на стороне клиента, и когда данный мозаичный элемент повторяется между двумя растровыми отображениями, сервер передает инструкцию клиенту для отображения кэшированного мозаичного элемента. Это может существенно сократить объем передачи для RDP сессии, в особенности, когда мозаичные элементы часто повторяются. Тем не менее, при такой схеме для кэширования мозаичных элементов должны быть выделены вычислительные ресурсы.

Сверх того, алгоритм разделения на мозаичные элементы часто реализуется в такой форме, чтобы максимизировать вероятность совпадения кэша. Чем меньше мозаичный элемент, тем выше шансы того, что он будет использован дважды (либо в этом кадре, либо в будущем кадре). Также часто существует минимальный полезный размер мозаичного элемента, поскольку если мозаичный элемент слишком маленький, обеспечивается лишь небольшое преимущество при совпадении кэша между двумя мозаичными элементами.

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

Одним из основных компонентов затрат обработки при кэшировании битового представления RDP является используемый хэш-алгоритм, то есть алгоритм, который преобразует данные изображения большего объема в данные с меньшим объемом, которые могут быть использованы в качестве индекса для сортированной структуры данных, такой как массив или дерево. Некоторые алгоритмы хэширования реализуют алгоритм Сцепления Блоков Шифра (Cipher Block Chaining, CBC) или некоторую вариацию алгоритма CBC. Тем не менее, это время обработки, используемое в алгоритме хэширования, может ограничивать масштабируемость сервера, поскольку все доступные ресурсы обработки могут использоваться сессиями RDP до истощения какого-либо другого ресурса, такого как полоса пропускания сети сервера. Это время обработки также увеличивает время, необходимое для кодирования кадра изображения, скорость, на которой эти кадры могут быть произведены и переданы клиенту (частоту кадров в единицах кадров в секунду).

Увеличение скорости алгоритма хэширования при существующих параллельных процессорах представляется сложным, поскольку хэш-алгоритм CBC, как правило, является последовательным, из-за чего его обработка неэффективна при параллельной обработке, такой как обработка на процессоре на базе архитектуры с Одним Потоком Команд и Множеством Потоков Данных (Single Instruction Multiple Data, SIMD).

Существует класс процессоров, известных как векторные процессоры, которые содержат инструкции SIMD в своей Структуре Системы Команд (Instruction Set Architecture, ISA). Дополнительные команды Streaming SIMD Extensions (SSE), такие как инструкции SSE 4.2 в некоторых ISA-процессорах INTEL™ x86 ISA, таких как процессор NEHALEM™, являют собой форму этих инструкций SIMD. Эти процессоры способны повысить скорость обработки определенных типов данных, поскольку они могут оперировать сразу большим объемом данных. Например, в случае обработки изображения, вместо оперирования одним пикселем за раз, SIMD-процессор может оперировать несколькими пикселями параллельно посредством одной инструкции. Это не только повышает эффективность обработки самой инструкции, но также может сократить время, затрачиваемое на извлечение данных из памяти.

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

Сущность изобретения

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

Настоящие способы полезны также в других сценариях, сверх классификации мозаичных элементов RDP, при условии, что они обеспечивают увеличение скорости хэширования при некотором увеличении частоты конфликтов совпадений. Это увеличение частоты конфликтов совпадений крайне мало и составляет приблизительно (100/2^{^}192)%.

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

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

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

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

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

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

Краткое описание чертежей

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

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

Фиг.2 - пример операционных процедур для ускорения хэширования;

Фиг.3 - иллюстрация клиента и сервера, которые осуществляют связь посредством Протокола Удаленного Рабочего Стола (Remote Desktop Protocol, RDP), в котором используются вышеупомянутые способы ускоренного различения мозаичных элементов.

Подробное описание иллюстративных вариантов осуществления

Фиг.1 представляет собой структурную схему вычислительного устройства общего назначения, в котором могут быть реализованы способы, описанные в настоящем документе. Вычислительное окружение 120 системы является лишь одним примером подходящего вычислительного окружения, и оно не предназначено для определения ограничений объема использования или функциональных возможностей настоящего изобретения. Кроме того, вычислительное окружение 120 не должно быть интерпретировано как имеющее зависимость или требования, относящиеся к какому-либо компоненту или комбинациям компонентов, проиллюстрированных в примере рабочего окружения 120. В некоторых вариантах осуществления показанные вычислительные элементы могут включать в себе схемы, сконфигурированные так, чтобы реализовывать конкретные аспекты настоящего раскрытия. Например, термин "схема", используемый в настоящем раскрытии, может включать в себя специализированные аппаратные компоненты, сконфигурированные так, чтобы выполнять функции посредством внутреннего программного обеспечения или переключателей. В других примерах осуществления термин "схема" может включать в себя процессорный блок общего назначения, память и т.п., конфигурируемые программными инструкциями, которые реализуют логику, действующую для выполнения функций. В примерах осуществления, где схемы включают в себя комбинацию аппаратного обеспечения и программного обеспечения, может быть написан исходный код, реализующий логику, и этот исходный код может быть компилирован в машиночитаемый код, который может обрабатываться процессорным блоком общего назначения. Специалистам в данной области техники будет очевидно, что современный уровень техники дошел до такого уровня, когда между аппаратным обеспечением, программным обеспечением или комбинацией аппаратного/программного обеспечений существует лишь небольшая разница, и выбор аппаратной или программной реализации конкретных функций выполняет конструктор. Более конкретно, специалистам в данной области техники будет очевидно, что программный процесс может быть трансформирован в эквивалентную аппаратную структуру, а аппаратная структура в свою очередь может быть трансформирована в эквивалентный программный процесс. Таким образом, выбор аппаратной или программной реализации остается за конструктором.

Компьютер 141, как правило, включает в себя ряд машиночитаемых средств. Машиночитаемые средства могут представлять собой любое доступное средство, к которому компьютер 141 может выполнить доступ, и они включают в себя как энергозависимые, так и энергонезависимые средства, съемные и несъемные средства. Системная память 122 включает в себя компьютерное средство хранения в форме энергозависимой и/или энергонезависимой памяти, такой как ПЗУ 123 и ОЗУ 160. Базовая система 124 ввода/вывода (BIOS), содержащая базовые рутинные процедуры, которые помогают передавать информацию между элементами в компьютере 141, как, например, во время загрузки, как правило, храниться в ПЗУ 123. ОЗУ 160, как правило, содержит данные и/или программные модули, которые непосредственно доступны и/или задействованы процессорным блоком 159. В качестве примера, но не ограничиваясь этим, Фиг.1 иллюстрирует операционную систему 125, прикладные программы 126, другие программные модули 127 и программные данные 128.

Компьютер 141 может также включать в себя другое съемное/несъемное энергозависимое/энергонезависимое компьютерное средство хранения. Исключительно в качестве примера, Фиг.1 иллюстрирует привод 138 жесткого диска, который считывает с или записывает на несъемный, энергонезависимый магнитный носитель, привод 139 магнитного диска, который считывает с или записывает на съемный, энергонезависимый магнитный диск 154, и привод 140 оптического диска, который считывает с или записывает на съемный, энергонезависимый оптический диск 153, такой как CD-ROM или другой оптический носитель информации. Другие съемные/несъемные, энергозависимые/энергонезависимые компьютерные носители информации, которые могут быть использованы в примере рабочего окружения, включают в себя, но не ограничиваются перечисленным, кассеты с магнитной лентой, карты флэш-памяти, цифровые универсальные диски, цифровые видео ленты, твердотельные ОЗУ, твердотельные ПЗУ и т.п. Привод 138 жесткого диска, как правило, соединен с системной шиной 121 через интерфейс несъемной памяти, такой как интерфейс 134, а привод 139 магнитного диска и привод 140 оптического диска, как правило, соединены с системной шиной 121 посредством интерфейса съемной памяти, такого как интерфейс 135.

Приводы и связанные с ними компьютерные носители информации, описанные выше и проиллюстрированные на Фиг.1, предоставляют хранилище машиночитаемых команд, структур данных, программных модулей и других данных для компьютера 141. На Фиг.1, например, привод 138 жесткого диска проиллюстрирован, как хранящий операционную систему 158, прикладные программы 157, другие программные модули 156 и программные данные 155. Следует отметить, что эти компоненты могут быть такими же, как операционная система 125, прикладные программы 126, другие программные модули 127 и программные данные 128, или же отличаться от них. Операционная система 158, прикладные программы 157, другие программные модули 156 и программные данные 155 обозначены различными номерами, чтобы проиллюстрировать, что, по меньшей мере, они представляют собой разные копии. Пользователь может вводить команды и информацию в компьютер 141 через устройства ввода, такие как клавиатура 151 и указывающее устройство 152, такое как мышь, трекбол или сенсорная панель. Другие устройства ввода (не показаны) могут включать в себя микрофон, джойстик, игровой планшет, спутниковую антенну, сканер или т.п. Эти и другие устройства ввода часто соединяются с процессорным блоком 159 через интерфейс 136 ввода пользователя, который соединен с системной шиной, но они также могут быть соединены посредством другого интерфейса и структур шины, такой как параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 142 или другой тип устройства отображения также соединен с системной шиной 121 посредством интерфейса, такого как видео интерфейс 132. В добавление к монитору компьютеры могут также включать в себя другие периферийные устройства вывода, такие как громкоговорители 144 и принтер 143, которые могут быть соединены через интерфейс 133 периферийных устройств вывода.

Компьютер 141 может работать в сетевом окружении, используя логические соединения с одним или более удаленными компьютерами, такими как удаленный компьютер 146. Удаленный компьютер 146 может быть персональным компьютером, сервером, маршрутизатором, сетевым персональным компьютером, устройством однорангового узла или другим обычным сетевым узлом, и он, как правило, включает в себя многие или все элементы, описанные выше относительно компьютера 141, хотя на Фиг.1 проиллюстрировано только устройство 147 памяти. Логические соединения, изображенные на Фиг.1, включают в себя локальную сеть (Local Area Network, LAN) 145 и глобальную сеть (Wide Area Network, WAN) 149, но они также могут включать в себя другие сети. Подобные сетевые окружения типичны для контор, компьютерных сетей масштаба предприятия, интранета и Интернета.

При использовании в сетевом окружении локальной сети компьютер 141 соединяется с локальной сетью 145 через сетевой интерфейс или адаптер 137. При использовании в сетевом окружении глобальной сети компьютер 141, как правило, включает в себя модем 150 или иное средство для установления связи через глобальную сеть 149, такую как Интернет. Модем 150, который может быть внутренним или внешним, может быть соединен с системной шиной 121 посредством интерфейса 136 ввода пользователя, или иного подходящего механизма. В сетевом окружении программные модули, изображенные относительно компьютера 141, или их части могут храниться в удаленном устройстве памяти. В качестве примера, но не ограничиваясь этим, Фиг.1 иллюстрирует удаленные прикладные программы 148 как находящиеся в устройстве 147 памяти. Очевидно, что показанные сетевые соединения представляют собой лишь примеры, и могут быть использованы другие средства для установления линии связи между компьютерами.

Фиг.2 представляет собой пример операционных процедур для ускорения хэширования. Процесс последовательного хэширования может принимать по одному Двойному Слову ((Double Word, DWORD); во многих системах его длина составляет 32 бита) данных изображения в направлении с начала изображения в конец изображения. В результате будет вычислен один ключ для этого изображения, который обновляется по каждому новому DWORD изображения, которое подвергается обработке. В противоположность этому, в настоящих иллюстративных процедурах обрабатывается сразу множество DWORD. В одном варианте осуществления, где DWORD содержит 32 бита и процессор может работать одновременно с 128 битами, одновременно обрабатываемый объем данных может составлять четыре DWORD. Эти процедуры держат четыре частичных ключа для изображения - по одному ключу, соответствующему каждому DWORD, обрабатываемому параллельно - и эти четыре частичных ключа могут быть скомбинированы после завершения обработки всего изображения, чтобы произвести финальный ключ.

Опциональная операция 202 иллюстрирует выполнение выбора первого случайного числа и второго случайного числа, которое отличается от упомянутого первого числа.

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

Операция 206 иллюстрирует группирование изображения в, по меньшей мере, одну группу, содержащую некоторое количество битов изображения. Процессор может оперировать более чем одним битом данных за один раз. Например, 128-битный процессор может одновременно оперировать 128 битами данных. То есть, этот процессор имеет "битовую ширину" в 128 битов. Эти 128 битов необязательно входят в состав одной и той же структуры данных, такой как структура, которая представляет 128-битное число. Скорее, эти 128 битов могут содержать множество элементов данных, таких как четыре дискретных 32-битных целых или восемь дискретных 16-битных целых. В такой ситуации существуют инструкции, чтобы результат этой операции (такой как умножение или логический сдвиг) не переполнял прилегающее целое в этих 128 битах, когда операция выполняется по группе из четырех 32-битных целых.

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

В одном варианте осуществления упомянутое изображение содержит мозаичный элемент согласно Протоколу Удаленного Рабочего Стола (Remote Desktop Protocol, RDP), причем этот мозаичный элемент содержит растровое представление. Мозаичный элемент может содержать подгруппу кадра, где кадр, как правило, содержит окно приложения. В одном типовом варианте осуществления кадр разделяется на множество прямоугольных мозаичных элементов, и клиенту необходимо передавать только те мозаичные элементы, которые изменились.

В одном варианте осуществления, где изображение не выровнено по линиям выравнивания, первые биты изображения до границы первого бита хэшируются по алгоритму Сцепления Блоков Шифра (Cipher Block Chaining, CBC), чтобы произвести предварительный первый ключ и предварительный второй ключ. Например, в случае когда операции параллельно выполняются по 128 битам и когда изображение не выровнено по 128-битной границе, если 56 битов изображения располагаются до первой 128-битной границы в изображении, то эти 56 битов хэшируются согласно последовательному алгоритму CBC и полученные в результате предварительный первый ключ и предварительный второй ключ комбинируются с результирующими первым ключом и вторым ключом, соответственно, из последующих операций путем последовательного алгоритма CBC.

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

В одном варианте осуществления первый ключ модифицируется посредством начальной величины путем выполнения операции исключающего ИЛИ на первом ключе и начальной величине, а второй ключ модифицируется посредством начальной величины путем выполнения операции исключающего ИЛИ на втором ключе и начальной величине. Исключающее ИЛИ являет собой битовую операцию, где результат двух вводов равен 1, если один и только один из этих вводов также равен 1. Например, 0^∧0=0, 0^∧1=1, 1^∧0=1 и 1^∧1=0, где оператор "^∧" обозначает операцию исключающего ИЛИ.

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

В одном варианте осуществления хэширование выполняется по алгоритму Сцепления Блоков Шифра (Cipher Block Chaining, CBC).

Опциональная операция 210 иллюстрирует установку первого ключа DWORD на основании размера битов каждого DWORD первого ключа и установку второго ключа DWORD на основании размера битов каждого DWORD второго ключа.

Когда первый ключ и второй ключ содержат меньше битов, чем битовая ширина процессора, вычисляются частичные ключи. После обработки всего изображения эти частичные ключи используются для определения целого первого ключа и целого второго ключа. Здесь рассматривается один вариант осуществления, где первый ключ и второй ключ содержат по 32 бита и битовая ширина составляет 128 битов. В этом варианте осуществления 128 битов изображения обрабатываются одновременно, в результате чего получается четыре 32-битных частичных первых ключа и четыре 32-битных частичных вторых ключа. После завершения обработки всего изображения каждый из этих четырех частичных ключей используется для определения целого ключа или первого ключа DWORD и второго ключа DWORD.

В одном варианте осуществления четыре частичных первых ключа используются для определения первого ключа DWORD путем применения к ним операции исключающего ИЛИ. Если упомянутые четыре частичных первых ключа выражаются как Key1[0], Key1[1], Key1[2] и Key1[3], то эта операция логически может быть выражена как Key1[0] ^∧ Key1[1] ^∧ Key1[2] ^∧ Key1[3].

В одном варианте осуществления четыре частичных первых ключа используются для определения первого ключа DWORD путем их комбинирования с использованием последовательного хэш-алгоритма CBC. В одном варианте осуществления Key1[0] подвергается CBC-хэшированию посредством Key1[1], результат чего подвергается CBC-хэшированию посредством Key1[2], результат чего подвергается CBC-хэшированию посредством Key1[3].

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

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

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

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

Когда каждый ключ содержит 32 бита, большой ключ содержит 64 бита, так что для большого ключа существует 2^∧64 возможных значений. В одном варианте осуществления существует возможность конфликта (ситуации, когда два разных мозаичных элемента соответствуют одному и тому же большому ключу), но вероятность этого настолько мала (приблизительно 1 из 2^∧64), что вычислительные ресурсы, необходимые для детектирования таких конфликтов, существенно превосходят пользу от детектирования конфликта и идентификации корректного изображения мозаичного элемента, так что конфликты игнорируются и может быть использовано некорректное изображение.

Операция 216 иллюстрирует кодирование изображения. В одном варианте осуществления кодирование изображения выполняется по схеме Кодирования Длин серий (Run-Length Encoding, RLE). В одном варианте осуществления разные части изображения могут кодироваться посредством разных кодеков. Например, если часть изображения должна быть отображена без потерь в качестве, например, в случае рентгеновского снимка в медицинской сфере, оно может быть закодировано посредством кодека без потерь. Другая часть изображения может представлять черный текст на белом фоне, и кодирование этой части по алгоритму RLE даст наибольший эффект. В этом случае эти два кодека могут использоваться на соответствующих частях изображения. В одном варианте осуществления цветовые каналы изображения разделены. RGBA-изображение разделяется на отдельные каналы: красного (R), зеленого (G), синего (B) цветов и альфа-канал (A), и каждый из этих каналов кодируется по отдельности.

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

Фиг.3 представляет собой иллюстрацию клиента и сервера, которые осуществляют связь посредством Протокола Удаленного Рабочего Стола (Remote Desktop Protocol, RDP), в котором используются вышеупомянутые способы ускоренного различения мозаичных элементов. Сервер 302 содержит RDP-сервер 304, базу 306 данных ключей и, по меньшей мере, одно растровое изображение 308. Изображение 308 разделяется на, по меньшей мере, один мозаичный элемент 310, причем каждый мозаичный элемент содержит растровое представление. Сервер 302 осуществляет связь с клиентом 314 через сеть 312 связи. Клиент 314 содержит RDP-клиент 316 и базу 318 данных мозаичных элементов, причем клиент 314 соединен с устройством 320 отображения.

В RDP-сессии между клиентом 314 и сервером 302 сервер передает клиенту информацию изображения через сеть 312, что соответствует обработке, которая выполняется сервером 302. Например, клиент 314 может иметь RDP-сессию, где на сервере исполняется текстовый редактор. Клиент 314 передает в сервер 302 команды, такие как ввод рядов символов в текстовом редакторе в текущей позиции редактирования или открытие нового файла. Эти команды обрабатываются на сервере 302, и результирующий вывод отображения передается обратно клиенту 314 для отображения на устройстве 320 отображения. В таком варианте осуществления изображение 308 может содержать окно приложения упомянутого текстового редактора на заданный момент времени. Если пользователь добавляет новый текст вблизи нижней части окна приложения, то верхняя часть окна приложения может не изменяться в ближайшем будущем. Так, изображение 308 может быть разделено на мозаичные элементы 310, и когда множество изображений 308 передается клиенту 314 в течение некоторого времени, каждое изображение 308 передается как множество мозаичных элементов 310, причем требуется передавать только те мозаичные элементы 310, которые отличаются от предыдущих мозаичных элементов 310. Клиент 314 может кэшировать ранее принятые мозаичные элементы 310 в кэш-памяти 318 мозаичных элементов, и если какой-либо мозаичный элемент 310 повторяется, то сервер 302 может передать клиенту 314 индикацию этого мозаичного элемента, а не сам мозаичный элемент 308. Этот первый мозаичный элемент, который находится в кэш-памяти 318 мозаичных элементов, необязательно находится в том же месте, что и повторяющийся мозаичный элемент. Например, в случае нового документа в сессии редактирования текста, большинство мозаичных элементов будут соответствовать пробелам, так что один мозаичный элемент чистого белого цвета может использоваться множество раз для всех этих мозаичных элементов.

Первый раз, когда сервер 302 получает запрос для изображения 308, оно берет первый мозаичный элемент 310 и хэширует его, чтобы определить большой ключ. Если сервер 306 хэширует мозаичный элемент 310 согласно способам, описанным со ссылкой на Фиг.2, упомянутый ключ может содержать первый ключ и второй ключ. Далее он использует RDP-сервер 304, чтобы передать этот мозаичный элемент RDP-клиенту 316 вместе с индикацией места в изображении, где должен находиться этот мозаичный элемент 310. Большой ключ также сохраняется в базе данных 306 ключей. База данных ключей может содержать множество структур данных для хранения целых, например в форме дерева.

Для каждого последующего мозаичного элемента 310 сервер 302 определяет большой ключ и далее сравнивает его с базой 306 данных ключей. Если совпадений нет, то это указывает на то, что мозаичный элемент, представляющий одно и то же изображение, ранее не был передан клиенту 314, и сервер 302 передает этот мозаичный элемент клиенту 314 и сохраняет большой ключ к нему в базе 306 данных ключей, как описано выше. Клиент принимает мозаичный элемент в RDP-клиенте 316 и кэширует его в кэш-памяти 318 мозаичных элементов вместе с большим ключом. Этот большой ключ может быть использован как ключ для нахождения изображения в кэш-памяти 318 мозаичных элементов, то есть он может использоваться как индекс к хэш-таблице.

Если для этого мозаичного элемента есть совпадение в базе 306 данных ключей, то это означает, что сервер 302 ранее уже передал мозаичный элемент, представляющий то же изображение, что и данный мозаичный элемент. Так, вместе того чтобы передать клиенту 314 этот мозаичный элемент 310, в целях экономии ресурсов сети сервер 302 передает клиенту 314 соответствующий большой ключ, который содержит меньший объем данных. Если первый ключ и второй ключ содержат по 32 бита, то большой ключ будет содержать 64 бита. Клиент 314 принимает этот ключ и начальную величину в RDP-клиенте 316, который использует этот большой ключ, чтобы найти соответствующий мозаичный элемент в кэш-памяти 320 мозаичных элементов.

Таким образом, RDP-клиент 314 получает либо сам мозаичный элемент, либо он получает соответствующий большой ключ и выполняет поиск мозаичного элемента в кэш-памяти 318 мозаичных элементов. Вместе с мозаичным элементом или большим ключом RDP-клиент 316 получает индикацию части изображения 308, которой принадлежит этот мозаичный элемент 310. Далее RDP-клиент 316 отображает этот мозаичный элемент 310 в подходящей части изображения на клиентском устройстве 320 отображения.

Пример инструкций

Ниже приведен пример псевдокода в синтаксисе высокоуровневого языка программирования типа C. Этот псевдокод при исполнении на векторном процессе обрабатывает изображение согласно варианту осуществления настоящего раскрытия, как указано в подробном описании Фиг.2.

_inline void_fastcall NextCBC64SSE(

CBC64Context *pContext,

Заключение

Несмотря на то что настоящее раскрытие было описано в связи с предпочтительными вариантами осуществления с различных фигур, следует понимать, что могут использоваться другие схожие варианты осуществления или в описанном варианте осуществления могут быть выполнены модификации и дополнения для выполнения такой же функции настоящего раскрытия. Следовательно, настоящее раскрытие не ограничено каким-либо одним аспектом и оно должно быть истолковано в широком смысле и объеме согласно прилагаемой формуле изобретения. Например, различные описанные выше процедуры могут быть реализованы посредством аппаратного обеспечения или программного обеспечения, либо их комбинации. Таким образом, способы и устройство раскрытых вариантов осуществления или их определенные аспекты или части могут принять форму программного кода (то есть, инструкций), реализуемого в вещественных носителях, таких как дискеты, диски CD-ROM, жесткие диски или любое другое машиночитаемое средство хранения. Когда этот программный код загружается и исполняется машиной, такой как компьютер, эта машина становится устройством, сконфигурированным для реализации раскрытых вариантов осуществления. В добавление к конкретным реализациям, в явной форме раскрытым выше, специалистам в данной области техники также будут очевидны другие аспекты и реализации. Вышеприведенная спецификация и проиллюстрированные реализации должны рассматриваться только в качестве примеров.

Изобретение относится к вычислительной технике. Технический результат заключается в ускорении хеширования. Компьютерно-реализуемый способ классифицирования изображения в системе параллельной обработки, имеющей битовую ширину, соответствующую количеству битов, которые процессор системы параллельной обработки может обрабатывать единовременно, в котором посредством системы параллельной обработки разделяют изображение на две группы, причем каждая группа содержит количество битов изображения, равное битовой ширине; для каждой группы посредством системы параллельной обработки выполняют хеширование, в котором: устанавливают новое значение начальной величины равным второе случайное число плюс умноженная на первое случайное число сумма значения, являющегося двоичным выражением группы, и текущего значения начальной величины, устанавливают новое значение первого ключа равным текущему значению первого ключа, модифицированному начальной величиной, и устанавливают новое значение второго ключа равным текущему значению второго ключа, модифицированному начальной величиной; и после выполнения хеширования, посредством системы параллельной обработки сохраняют большой ключ, содержащий первый ключ и второй ключ, в компьютерной памяти. 3 н. и 17 з.п. ф-лы, 3 ил.

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

2. Способ по п.1, дополнительно содержащий этап, на котором передают изображение на клиентский компьютер через сеть связи.

3. Способ по п.2, в котором при передаче изображения на клиентский компьютер через сеть связи изображение передают на клиентский компьютер в качестве реакции на определение того, что большой ключ не совпадает с каким-либо другим большим ключом в компьютерной памяти.

4. Способ по п.3, дополнительно содержащий этап, на котором передают большой ключ на клиентский компьютер.

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

6. Способ по п.2, дополнительно содержащий этап, на котором кодируют изображение до его передачи на клиентский компьютер.

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

8. Способ по п.1, в котором первый ключ модифицируется начальной величиной путем выполнения операции исключающего ИЛИ в отношении первого ключа и начальной величины, а второй ключ модифицируется начальной величиной путем выполнения операции исключающего ИЛИ в отношении второго ключа и начальной величины.

9. Способ по п.1, в котором изображение имеет начало и конец и упомянутые операции, выполняемые для каждой группы, сначала выполняются для группы, которая является ближайшей к началу и для которой упомянутые операции, выполняемые для каждой группы, еще не были выполнены.

10. Способ по п.1, дополнительно содержащий этап, на котором, в качестве реакции на определение того, что при разделении размера изображения на битовую ширину остается ненулевое остаточное количество битов, подвергают хешированию это остаточное количество битов посредством последовательного алгоритма Сцепления Блоков Шифра (СВС), чтобы получить пост-первый ключ и пост-второй ключ, определяют первый ключ на основе пост-первого ключа и определяют второй ключ на основе пост-второго ключа.

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

12. Способ по п.1, в котором при выполнении хеширования выполняют вариант Сцепления Блоков Шифра (СВС).

13. Способ по п.1, в котором изображение содержит экранный снимок.

14. Способ по п.1, в котором изображение содержит мозаичный элемент в Протоколе Удаленного Рабочего Стола (RDP).

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

16. Система по п.15, в которой в памяти содержатся исполняемые процессором инструкции, которые при их исполнении процессором предписывают системе, по меньшей мере:
кодировать изображение и
посылать кодированное изображение на клиент по сети связи в соответствии с Протоколом Удаленного Рабочего Стола (RDP).

17. Система по п.15, в которой пиксел изображения содержит 32 бита, а битовая ширина составляет 128 битов.

18. Система по п.17, в которой в памяти содержатся исполняемые процессором инструкции, которые при их исполнении процессором предписывают системе, по меньшей мере:
определять, что изображение не выровнено до упомянутого разделения изображения, и выполнять хеширование части изображения, которая находится перед первой границей выравнивания, с помощью последовательного алгоритма, чтобы получить предварительный первый ключ и предварительный второй ключ; и
комбинировать предварительный первый ключ с первым ключом и предварительный второй ключ со вторым ключом.

19. Система по п.15, в которой большой ключ сохраняется в хранилище больших ключей, когда большой ключ не совпадает ни с каким другим ключом в хранилище больших ключей.

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