Интересно, но тут задачи совсем другие.
В том проекте задача эмулировать чип с определенными характеристиками и для этого выделяются отдельные чипы.
Я же хотел иметь возможность добавить звук в существующие проекты без существенного изменения схемы. А качество звука и количество каналов настраивать по остаточному принципу, в зависимости от того, сколько ресурсов останется.
Интересный проект, хотя мне не очень понятно как его можно использовать. Слишком уж сложно заставить микроконтроллер делать что-то еще помимо воспроизведения музыки.
К тому же, формат MOD слишком тяжелый для маленьких микроконтроллеров, хоть и намного более универсальный.
А вот если бы его на Arduino портировать, то могло бы быть вполне годно. Там и 32кб флеша и 16МГц кварц из коробки.
При сдвиге вправо значение уменьшается в 2 раза, а мы можем хотеть иметь громкость, например, 87%.
Если упростить, то один сдвиг соответствует умножению на число, у которого только один бит равен 1, а остальные 0. Если нужно иметь возможность вычислять сэмпл для любого значения громкости, то надо будет делать до 8 сдвигов и мы получим то же умножение, только медленное.
И вообще, в AVR нет операции сдвига на произвольное количество битов. Можно только на 1 бит влево или на 1 бит вправо.
Запоминать уменьшеное значение семпла для уменьшения его позже тоже не получится. Wave table находится в програмной памяти и доступна только для чтения. И ее нужно было бы пересчитывать всю. И хранить отдельно для каждого канала.
Одну мелодию, там где много инструментов, я брал из своего старого проекта. Помню, что накидал данные в csv (строки — такты, столбцы — команды, подобно трекерной музыке) и потом перегнал в команды простым самописным конвертором. Конвертор уже где-то потерялся, но его не особо сложно написать заново.
Вторую мелодию позаимствовал из проэкта музкальной шкатулки, в ссылках есть. Опять же, наколеночный конвертор, показывать стыдно.
Коротенькие уведомления писал руками и тестировал в wavepot.
Писать конвертор из midi нет желания и вряд ли получится. Слишком специфические инструменты, ограничение на количество каналов и дискретизацию по тактам. Я думаю, что проще из трекерной музыки (например mod) конвертировать, но и там будет специфика.
Проект на гитхабе, можете попробовать померять.
Укажите 3 канала вместо 5 и можно включить интерполяцию. Или использовать Arduino на 16МГц как самый простой вариант.
Как мне кажется, смысла хранить по таблице для каждой ноты нет. Можно попробовать хранить по таблице на октаву. В каждой следующей уменьшать количество гармоник вдвое путем выбрасывания половины сэмплов а потом интерполировать обратно до 256 сэмплов. Это как самый простой вариант.
Использую одну таблицу. Но можно сделать и несколько с той же производительностью. Когда начинает играть следующая нота, то вызывается функция инструмента и там можно выбрать необходимый массив в зависимости от заданой ноты.
Интерполяцию значений между семплами можно включить (директива INTERPOLATE_WAVE), но производительность падает. Решил просто использовать более длинную таблицу в 256 значений, а интерполяцию провести перед помещением данных в таблицу.
Картинка не вставилась.
Но идея хороша, можете попробовать :)
Надо написать драйвер (каталог microsound/devices) и там просто выводить значение в порт.
Решение со щелчками на поверхности, я его даже реализовывал, но оно все-таки просаживало производительность. В какой-то момент я делал рефакторинг кода и оно мешало, убрал. Обратно запиливать не стал. В планах все-таки попробовать плавно уменьшать громкость перед следующей нотой, но там пока не очень очевидно как это сделать хорошо.
По поводу PWM — да, проблема есть. Но в коде именно за вывод звука отвечает драйвер (каталог microsound/devices), можно что-то другое подключить. Covox, например, как советуют ниже.
Спасибо за комментарий. Возможно, стоит как-то переименовать заголовок, чтобы не смущать тех, кто в теме. Я старался упростить для тех, кто не в теме, и описал только то, что используется.
Wavetable synthesis is fundamentally based on periodic reproduction of an arbitrary, single-cycle waveform.
По сути, тут периодическая функция — это не совсем функция, а как раз таблица значений амплитуды, 256 значений на период. А еще она работает не сама по себе, а в паре с функцией громкости от времени, которая тоже яавляется таблицей значений.
Возможно, существует более подходящий термин, но я его не знаю.
Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).
Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).
Как мне кажется, для таких случаев стоит использовать какой-то параметр уверености. Например, рассматривать 2 наиболее вероятных варианта. И не парсить слово, если у них ошибки достаточно близки.
Но тут, конечно, от задачи зависит. Где-то может быть нужно распарсить любой ценой, а где-то неправильный или неоднозначный парсинг недопустим.
Идея интересная. У меня получился результат примерно на уровне моего последнего решения. Но в тут таки можно использовать память по полной и поместить 21 значения в long.
Из минусов такого подхода — надо подбирать размер массива для конкретного железа. У меня получился лучший результат при 2^12 интов, по 4 трехбитных слова. При использовании 2^9 или 2^15 производительность становится хуже. Так же она становится хуже при использовании массива байтов вместо инта. На Вашем железе может быть по-другому.
Алгоритм простой, сначала посчитать разность (см. предыдуйие код, 2 первые строчки), а потом посуммировать из массива. Если захотите проверить, то разберетесь как это сделать :)
Ну и я бы рекомендовал все-таки проверить мои 2 последних решения на Ваших данных и Вашем железе. Даже если по скорости он окажется таким же, то по памяти будет выигрыш. И мне тоже хотелось бы узнать результат :)
Ваша задача не отпускает :)
Обнаружил, что джава считает Long.bitCount очень быстро, по крайней мере на моей системе. Скорее всего задействует SSE инструкции или типа того.
А в связи с этим открываются новые возможности по оптимизации:
public static long sumSqDiff(long l1, long l2) {
long sameSign100 = (~(l1 ^ l2)) & BITS_100;
// sum = l1 - l2
long sum = ((l1 | BITS_100) - (l2 & BITS_011)) ^ sameSign100;
// correct estimate: add cases for values +/-3
return Long.bitCount(((sum ^ (sum << 1)) & BITS_100) & (sum << 2)) * 8 + estimate(l1, l2);
}
public static long estimate(long l1, long l2) {
long xor = l1 ^ l2;
long ones = xor & BITS_001;
long res = Long.bitCount(ones);
xor &= ~(ones * 7);
long twos = xor & BITS_010;
res += Long.bitCount(twos) * 4;
xor &= ~(twos * 3);
res += Long.bitCount(xor) * 16;
return res;
}
Это пока самый быстрый код, который я смог получить на своей системе. Не факт что на Вашей системе будет так же.
Метод estimate медленнее, чем у Вас, но более точный. Из плюсов, можно грубо посчитать грубую оценку, а потом при необходимости досчитать. Хотя в Вашем случае выигрыш от такого подхода будет совсем небольшой.
Я понял.
Переписал Ваш код на джаву и проверил производительность с помощью JMH.
Реализация с циклом примерно в 2 раза медленнее моей 4хбитной реализации. Трехбитная реализация была медленнее, но у меня уже есть решение с оптимизацией. Новое решение даже чуть обгоняет четырехбитное (правда, не понимаю почему), но в нем на 25% больше данных, так что в итоге должно быть быстрее и с меньшим потреблением памяти. Грубый фильтр примерно в 6 раз быстрее моей самой быстрой реализации (но это в пересчете на один long а не на количество реальных данных в нем).
Вот результаты тестов:
public static final long BITS_001 = 0b001001001001001001001001001001001001001001001001001001001001001L;
public static final long BITS_010 = BITS_001 << 1;
public static final long BITS_100 = BITS_001 << 2;
public static final long BITS_011 = BITS_010 | BITS_001;
public static final long BITS_GROUP_0N =0b000111000111000111000111000111000111000111000111000111000111000L;
public static final long BITS_GROUP_0 = 0b111000111000111000111000111000111000111000111000111000111000111L;
public static final long BITS_GROUP_1 = 0b111000000111111000000111111000000111111000000111111000000111111L;
public static final long BITS_MUL = 0b000000000000001000000000001000000000001000000000001000000000001L;
public static long sumSqDiff(long l1, long l2) {
// Calculate same sign places
long sameSign100 = (~(l1 ^ l2)) & BITS_100;
// sum = l1 - l2
long sum = ((l1 | BITS_100) - (l2 & BITS_011)) ^ sameSign100;
// sum = abs(sum)
long sumNeg001 = (sum & BITS_100) >>> 2;
sum = (sum ^ (sumNeg001 * 7)) + sumNeg001;
// Calculate separate bits, prepare for multiplication
long b0 = (sum & BITS_001) * 3; // Bit 0b001 -> 0b011
long b1 = (sum & BITS_010) * 3; // Bit 0b010 -> 0b110
// mul011 = l1 * l1 (low 2 bits only)
long sumPart1 = sum & BITS_GROUP_0;
long sumPart2 = sum & BITS_GROUP_0N;
long res = ((sumPart1 << 1) & b1) + (sumPart1 & b0) +
((((sumPart2 << 1) & b1) + (sumPart2 & b0)) >>> 3);
// Calculate special case for value 4 = 0b100
long b2 = (sum & BITS_100) << 2;
res += (b2 + (b2 >>> 3)) & BITS_GROUP_0N;
// Combine alltogether
res = (res & BITS_GROUP_1) + ((res >>> 6) & BITS_GROUP_1);
res = (res * BITS_MUL) >>> 48;
return res & 0xFFF;
}
Статью писать я вряд ли буду, я не так много могу рассказать по этому поводу. Но могу порекомендовать отличную книгу по теме, называется Hacker's Delight или в русском переводе Алгоритмические трюки для программистов.
Странно, что нет повышения производительности. Возможно, что узкое место где-то не здесь. Попробуйте сравнить два (или три) решения без применения предварительного фильтра.
Я еще немного подчистил код для трехбитной реализации. Улучшение производительности в рамках погрешности, хотя вроде и есть.
public static long sumSqDiff(long l1, long l2) {
// l2 = -l2, inverse L2 to use sum instead of substraction
long l2NotZero001 = (l2 | (l2 >>> 1)) & BITS_001;
long l2Neg111 = (l2NotZero001 << 2) | (l2NotZero001 << 1) | l2NotZero001;
l2 = (l2 ^ l2Neg111) + l2NotZero001;
// Calculate where only one negative value is present (flip highest bit)
long oneNeg100 = (l1 ^ l2) & BITS_100;
// sum = l1 + l2
long sum = ((l1 & BITS_011) + (l2 & BITS_011)) ^ oneNeg100;
// sum = abs(sum)
long sumNeg100 = sum & BITS_100;
long sumNeg001 = sumNeg100 >>> 2;
long sumNeg111 = sumNeg100 | (sumNeg001 << 1) | sumNeg001;
sum = (sum ^ sumNeg111) + sumNeg001;
// Calculate separate bits, prepare for multiplication
long b0 = sum & BITS_001; // Bit 0b001
b0 = b0 | (b0 << 1); // Bit 0b001 -> 0b011
long b1 = sum & BITS_010; // Bit 0b010
b1 = b1 | (b1 >>> 1); // Bit 0b010 -> 0b011
long b2 = (sum & BITS_100) >>> 2; // Bit 0b100 -> 0b001
// mul011 = l1 * l1 (low 2 bits only)
long sumPart1 = sum & BITS_GROUP_0;
long sumPart2 = sum & BITS_GROUP_0N;
long res = ((sumPart1 & b1) << 1) + (sumPart1 & b0) +
((((sumPart2 & b1) << 1) + (sumPart2 & b0)) >>> 3);
// Calculate special case for value 4 = 0b100
b2 = (b2 + (b2 >>> 3)) & BITS_GROUP_0;
// Combine alltogether
res += b2 << 4;
res = (res & BITS_GROUP_1) + ((res >>> 6) & BITS_GROUP_1);
res = (res + (res >>> 12));
res = (res + (res >>> 24));
res = (res + (res >>> 48));
return res & 0xFFF;
}
Не сомневаюсь, что ради этого и писалась статья :)
И, раз уж Вы так хотели уложить данные в 3 бита, то это тоже можно сделать. Правда, только 20 штук в long, а не 21, если без костылей просаживающих производительность.
Значения такие же как и в предыдущем примере, [0b110, 0b111, 0b000, 0b001, 0b010]. И все так же без веток и циклов:
public static final long BITS_001 = 0b001001001001001001001001001001001001001001001001001001001001001L;
public static final long BITS_010 = BITS_001 << 1;
public static final long BITS_100 = BITS_001 << 2;
public static final long BITS_011 = BITS_010 | BITS_001;
public static final long BITS_GROUP_0N =0b000111000111000111000111000111000111000111000111000111000111000L;
public static final long BITS_GROUP_0 = 0b111000111000111000111000111000111000111000111000111000111000111L;
public static final long BITS_GROUP_1 = 0b111000000111111000000111111000000111111000000111111000000111111L;
public static final long BITS_GROUP_2 = 0b000111111111111000000000000111111111111000000000000111111111111L;
public static long sumSqDiff(long l1, long l2) {
// l2 = -l2, inverse L2 to use sum instead of substraction
long l2Neg001 = (l2 | (l2 >>> 1) | (l2 >>> 2)) & BITS_001;
long l2Neg111 = (l2Neg001 << 2) | (l2Neg001 << 1) | l2Neg001;
l2 = (l2 ^ l2Neg111) + l2Neg001;
// Calculate where substraction is needed (flip highest bit)
long oneNeg100 = (l1 ^ l2) & BITS_100;
// sum = l1 + l2
long sum = ((l1 & BITS_011) + (l2 & BITS_011)) ^ oneNeg100;
// sum = abs(sum)
long sumNeg001 = (sum & BITS_100) >>> 2;
long sumNeg111 = (sumNeg001 << 2) | (sumNeg001 << 1) | sumNeg001;
sum = (sum ^ sumNeg111) + sumNeg001;
// Calculate separate bits, prepare for multiplication
long b0 = sum & BITS_001; // Bit 0b001
b0 = b0 | (b0 << 1); // Bit 0b001 -> 0b011
long b1 = sum & BITS_010; // Bit 0b010
b1 = b1 | (b1 >>> 1); // Bit 0b010 -> 0b011
long b2 = (sum & BITS_100) >>> 2; // Bit 0b100 -> 0b001
// mul011 = l1 * l1 (low 2 bits only)
long sumPart1 = sum & BITS_GROUP_0;
long sumPart2 = sum & BITS_GROUP_0N;
long res = ((sumPart1 & b1) << 1) + (sumPart1 & b0) +
((((sumPart2 & b1) << 1) + (sumPart2 & b0)) >>> 3);
// Calculate special case for value 4 = 0b100
b2 = (b2 + (b2 >>> 3)) & BITS_GROUP_0;
b2 = (b2 + (b2 >>> 6)) & BITS_GROUP_1;
// Combine alltogether
res = (res + (res >>> 6)) & BITS_GROUP_1;
res += b2 << 4;
res = (res + (res >>> 12)) & BITS_GROUP_2;
res = (res + (res >>> 24));
res = (res + (res >>> 48));
return res & 0xFFF;
}
Не знаю как будет по скорости. Наверно можно еще что-то соптимизировать, но я пока пас. Скорее всего примерно так же, как и в предыдущем примере. Но памяти меньше.
Буду ждать от Вас результатов тестов.
Можно сумму квадратов разности посчитать без циклов и ветвлений. Скорее всего будет быстрее, чем в приведенном примере.
В данном случае для значений [-2..2] я использовал по 4 бита на число: [0b0110, 0b0111, 0b0000, 0b0001, 0b0010].
Идея использовать побитовую магию для паралельного подсчета всех полубайтов лонга одновременно.
Код на джаве:
Да, выше о нем уже упомянули. Постараюсь посмотреть исходники когда будет время.
Интересно, но тут задачи совсем другие.
В том проекте задача эмулировать чип с определенными характеристиками и для этого выделяются отдельные чипы.
Я же хотел иметь возможность добавить звук в существующие проекты без существенного изменения схемы. А качество звука и количество каналов настраивать по остаточному принципу, в зависимости от того, сколько ресурсов останется.
Интересный проект, хотя мне не очень понятно как его можно использовать. Слишком уж сложно заставить микроконтроллер делать что-то еще помимо воспроизведения музыки.
К тому же, формат MOD слишком тяжелый для маленьких микроконтроллеров, хоть и намного более универсальный.
А вот если бы его на Arduino портировать, то могло бы быть вполне годно. Там и 32кб флеша и 16МГц кварц из коробки.
Я не уверен, что правильно понял вопрос. Скорее всего, вы имеете в виду что-то типа:
Так не получится, так как:
Одну мелодию, там где много инструментов, я брал из своего старого проекта. Помню, что накидал данные в csv (строки — такты, столбцы — команды, подобно трекерной музыке) и потом перегнал в команды простым самописным конвертором. Конвертор уже где-то потерялся, но его не особо сложно написать заново.
Вторую мелодию позаимствовал из проэкта музкальной шкатулки, в ссылках есть. Опять же, наколеночный конвертор, показывать стыдно.
Коротенькие уведомления писал руками и тестировал в wavepot.
Писать конвертор из midi нет желания и вряд ли получится. Слишком специфические инструменты, ограничение на количество каналов и дискретизацию по тактам. Я думаю, что проще из трекерной музыки (например mod) конвертировать, но и там будет специфика.
Проект на гитхабе, можете попробовать померять.
Укажите 3 канала вместо 5 и можно включить интерполяцию. Или использовать Arduino на 16МГц как самый простой вариант.
Как мне кажется, смысла хранить по таблице для каждой ноты нет. Можно попробовать хранить по таблице на октаву. В каждой следующей уменьшать количество гармоник вдвое путем выбрасывания половины сэмплов а потом интерполировать обратно до 256 сэмплов. Это как самый простой вариант.
Использую одну таблицу. Но можно сделать и несколько с той же производительностью. Когда начинает играть следующая нота, то вызывается функция инструмента и там можно выбрать необходимый массив в зависимости от заданой ноты.
Интерполяцию значений между семплами можно включить (директива INTERPOLATE_WAVE), но производительность падает. Решил просто использовать более длинную таблицу в 256 значений, а интерполяцию провести перед помещением данных в таблицу.
О такой возможности я писал во вступлении.
Картинка не вставилась.
Но идея хороша, можете попробовать :)
Надо написать драйвер (каталог microsound/devices) и там просто выводить значение в порт.
Решение со щелчками на поверхности, я его даже реализовывал, но оно все-таки просаживало производительность. В какой-то момент я делал рефакторинг кода и оно мешало, убрал. Обратно запиливать не стал. В планах все-таки попробовать плавно уменьшать громкость перед следующей нотой, но там пока не очень очевидно как это сделать хорошо.
По поводу PWM — да, проблема есть. Но в коде именно за вывод звука отвечает драйвер (каталог microsound/devices), можно что-то другое подключить. Covox, например, как советуют ниже.
Спасибо за комментарий. Возможно, стоит как-то переименовать заголовок, чтобы не смущать тех, кто в теме. Я старался упростить для тех, кто не в теме, и описал только то, что используется.
Из вики:
По сути, тут периодическая функция — это не совсем функция, а как раз таблица значений амплитуды, 256 значений на период. А еще она работает не сама по себе, а в паре с функцией громкости от времени, которая тоже яавляется таблицей значений.
Возможно, существует более подходящий термин, но я его не знаю.
Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).
Как мне кажется, для таких случаев стоит использовать какой-то параметр уверености. Например, рассматривать 2 наиболее вероятных варианта. И не парсить слово, если у них ошибки достаточно близки.
Но тут, конечно, от задачи зависит. Где-то может быть нужно распарсить любой ценой, а где-то неправильный или неоднозначный парсинг недопустим.
Идея интересная. У меня получился результат примерно на уровне моего последнего решения. Но в тут таки можно использовать память по полной и поместить 21 значения в long.
Из минусов такого подхода — надо подбирать размер массива для конкретного железа. У меня получился лучший результат при 2^12 интов, по 4 трехбитных слова. При использовании 2^9 или 2^15 производительность становится хуже. Так же она становится хуже при использовании массива байтов вместо инта. На Вашем железе может быть по-другому.
Алгоритм простой, сначала посчитать разность (см. предыдуйие код, 2 первые строчки), а потом посуммировать из массива. Если захотите проверить, то разберетесь как это сделать :)
Ну и я бы рекомендовал все-таки проверить мои 2 последних решения на Ваших данных и Вашем железе. Даже если по скорости он окажется таким же, то по памяти будет выигрыш. И мне тоже хотелось бы узнать результат :)
Ваша задача не отпускает :)
Обнаружил, что джава считает Long.bitCount очень быстро, по крайней мере на моей системе. Скорее всего задействует SSE инструкции или типа того.
А в связи с этим открываются новые возможности по оптимизации:
Это пока самый быстрый код, который я смог получить на своей системе. Не факт что на Вашей системе будет так же.
Метод
estimateмедленнее, чем у Вас, но более точный. Из плюсов, можно грубо посчитать грубую оценку, а потом при необходимости досчитать. Хотя в Вашем случае выигрыш от такого подхода будет совсем небольшой.Я понял.
Переписал Ваш код на джаву и проверил производительность с помощью JMH.
Реализация с циклом примерно в 2 раза медленнее моей 4хбитной реализации. Трехбитная реализация была медленнее, но у меня уже есть решение с оптимизацией. Новое решение даже чуть обгоняет четырехбитное (правда, не понимаю почему), но в нем на 25% больше данных, так что в итоге должно быть быстрее и с меньшим потреблением памяти. Грубый фильтр примерно в 6 раз быстрее моей самой быстрой реализации (но это в пересчете на один long а не на количество реальных данных в нем).
Вот результаты тестов:
Ну и оптимизированый код:
Статью писать я вряд ли буду, я не так много могу рассказать по этому поводу. Но могу порекомендовать отличную книгу по теме, называется
Hacker's Delightили в русском переводеАлгоритмические трюки для программистов.Странно, что нет повышения производительности. Возможно, что узкое место где-то не здесь. Попробуйте сравнить два (или три) решения без применения предварительного фильтра.
Я еще немного подчистил код для трехбитной реализации. Улучшение производительности в рамках погрешности, хотя вроде и есть.
Не сомневаюсь, что ради этого и писалась статья :)
И, раз уж Вы так хотели уложить данные в 3 бита, то это тоже можно сделать. Правда, только 20 штук в long, а не 21, если без костылей просаживающих производительность.
Значения такие же как и в предыдущем примере, [0b110, 0b111, 0b000, 0b001, 0b010]. И все так же без веток и циклов:
Не знаю как будет по скорости. Наверно можно еще что-то соптимизировать, но я пока пас. Скорее всего примерно так же, как и в предыдущем примере. Но памяти меньше.
Буду ждать от Вас результатов тестов.
Можно сумму квадратов разности посчитать без циклов и ветвлений. Скорее всего будет быстрее, чем в приведенном примере.
В данном случае для значений [-2..2] я использовал по 4 бита на число: [0b0110, 0b0111, 0b0000, 0b0001, 0b0010].
Идея использовать побитовую магию для паралельного подсчета всех полубайтов лонга одновременно.
Код на джаве:
Надеюсь, у автора будет возможность проверить и написать результат.