Piano: New timing system and zoomable piano roll

This patch allows roll notes to be of different sizes. This necessitates
a new internal representation of time. BPM and time signatures are
mostly implemented but not exposed.

Roll notes are now sample-accurate and the grid is aligned to 60 BPM
4/4. The roll is divided by the time signature raised to some power of
2, giving the musical divisions of (in the case of 4/4) 16, 32, 64 etc.

Before, our timing was derived from the buffer size and we relied on
that to implement delay. Delay has been rewritten to be sample-granular.
It's now exposed as the proper "divisions of a beat".
Something to be wary of is that the last buffer in the loop is also used
for the start of the next loop. In other words, we loop mid-buffer. This
means we write WAVs with a tiny bit of silence due to breaking the loop
after filling half a buffer.

The data structure for the roll is an array of SinglyLinkedLists of
RollNotes. Separating by pitch (via the array layout) makes insertion
much simpler and faster. Using sorted lists (and thus
SinglyLinkedListIterators) to do lookups is very quick as you know the
sample of the next note and can just compare it to the current sample. I
implemented this with HashMaps and the cost of lookups was abysmal. I
also tried a single SinglyLinkedList and the insertion code got even
more complicated than it already is.

1 files changed, 104 insertions, 24 deletions

diff --git a/Applications/Piano/RollWidget.cpp b/Applications/Piano/RollWidget.cpp
index 03b87413ac..b46989b0f1 100644
--- a/Applications/Piano/RollWidget.cpp
+++ b/Applications/Piano/RollWidget.cpp
@@ -29,9 +29,13 @@
 #include "AudioEngine.h"
 #include <LibGUI/Painter.h>
 #include <LibGUI/ScrollBar.h>
+#include <math.h>
 
 constexpr int note_height = 20;
+constexpr int max_note_width = note_height * 2;
 constexpr int roll_height = note_count * note_height;
+constexpr int horizontal_scroll_sensitivity = 20;
+constexpr int max_zoom = 1 << 8;
 
 RollWidget::RollWidget(AudioEngine& audio_engine)
     : m_audio_engine(audio_engine)
@@ -47,10 +51,21 @@ RollWidget::~RollWidget()
 
 void RollWidget::paint_event(GUI::PaintEvent& event)
 {
-    int roll_width = widget_inner_rect().width();
-    double note_width = static_cast<double>(roll_width) / horizontal_notes;
-
-    set_content_size({ roll_width, roll_height });
+    m_roll_width = widget_inner_rect().width() * m_zoom_level;
+    set_content_size({ m_roll_width, roll_height });
+
+    // Divide the roll by the maximum note width. If we get fewer notes than
+    // our time signature requires, round up. Otherwise, round down to the
+    // nearest x*(2^y), where x is the base number of notes of our time
+    // signature. In other words, find a number that is a double of our time
+    // signature. For 4/4 that would be 16, 32, 64, 128 ...
+    m_num_notes = m_roll_width / max_note_width;
+    int time_signature_notes = beats_per_bar * notes_per_beat;
+    if (m_num_notes < time_signature_notes)
+        m_num_notes = time_signature_notes;
+    else
+        m_num_notes = time_signature_notes * pow(2, static_cast<int>(log2(m_num_notes / time_signature_notes)));
+    m_note_width = static_cast<double>(m_roll_width) / m_num_notes;
 
     // This calculates the minimum number of rows needed. We account for a
     // partial row at the top and/or bottom.
@@ -63,25 +78,29 @@ void RollWidget::paint_event(GUI::PaintEvent& event)
     int notes_to_paint = paint_area / note_height;
     int key_pattern_index = (notes_per_octave - 1) - (note_offset % notes_per_octave);
 
+    int x_offset = horizontal_scrollbar().value();
+    int horizontal_note_offset_remainder = fmod(x_offset, m_note_width);
+    int horizontal_paint_area = widget_inner_rect().width() + horizontal_note_offset_remainder;
+    if (fmod(horizontal_paint_area, m_note_width) != 0)
+        horizontal_paint_area += m_note_width;
+    int horizontal_notes_to_paint = horizontal_paint_area / m_note_width;
+
     GUI::Painter painter(*this);
     painter.translate(frame_thickness(), frame_thickness());
-    painter.translate(0, -note_offset_remainder);
+    painter.translate(-horizontal_note_offset_remainder, -note_offset_remainder);
+    painter.add_clip_rect(event.rect());
 
     for (int y = 0; y < notes_to_paint; ++y) {
         int y_pos = y * note_height;
-        for (int x = 0; x < horizontal_notes; ++x) {
+        for (int x = 0; x < horizontal_notes_to_paint; ++x) {
             // This is needed to avoid rounding errors. You can't just use
-            // note_width as the width.
-            int x_pos = x * note_width;
-            int next_x_pos = (x + 1) * note_width;
+            // m_note_width as the width.
+            int x_pos = x * m_note_width;
+            int next_x_pos = (x + 1) * m_note_width;
             int distance_to_next_x = next_x_pos - x_pos;
             Gfx::Rect rect(x_pos, y_pos, distance_to_next_x, note_height);
 
-            if (m_audio_engine.roll_note(y + note_offset, x) == On)
-                painter.fill_rect(rect, note_pressed_color);
-            else if (x == m_audio_engine.current_column())
-                painter.fill_rect(rect, column_playing_color);
-            else if (key_pattern[key_pattern_index] == Black)
+            if (key_pattern[key_pattern_index] == Black)
                 painter.fill_rect(rect, Color::LightGray);
             else
                 painter.fill_rect(rect, Color::White);
@@ -94,6 +113,31 @@ void RollWidget::paint_event(GUI::PaintEvent& event)
             key_pattern_index = notes_per_octave - 1;
     }
 
+    painter.translate(-x_offset, -y_offset);
+    painter.translate(horizontal_note_offset_remainder, note_offset_remainder);
+
+    for (int note = note_count - (note_offset + notes_to_paint); note <= (note_count - 1) - note_offset; ++note) {
+        for (auto roll_note : m_audio_engine.roll_notes(note)) {
+            int x = m_roll_width * (static_cast<double>(roll_note.on_sample) / roll_length);
+            int width = m_roll_width * (static_cast<double>(roll_note.length()) / roll_length);
+            if (x + width < x_offset || x > x_offset + widget_inner_rect().width())
+                continue;
+            if (width < 2)
+                width = 2;
+
+            int y = ((note_count - 1) - note) * note_height;
+            int height = note_height;
+
+            Gfx::Rect rect(x, y, width, height);
+            painter.fill_rect(rect, note_pressed_color);
+            painter.draw_rect(rect, Color::Black);
+        }
+    }
+
+    int x = m_roll_width * (static_cast<double>(m_audio_engine.time()) / roll_length);
+    if (x > x_offset && x <= x_offset + widget_inner_rect().width())
+        painter.draw_line({ x, 0 }, { x, roll_height }, Gfx::Color::Black);
+
     GUI::Frame::paint_event(event);
 }
 
@@ -102,25 +146,61 @@ void RollWidget::mousedown_event(GUI::MouseEvent& event)
     if (!widget_inner_rect().contains(event.x(), event.y()))
         return;
 
-    int roll_width = widget_inner_rect().width();
-    double note_width = static_cast<double>(roll_width) / horizontal_notes;
-
     int y = (event.y() + vertical_scrollbar().value()) - frame_thickness();
     y /= note_height;
 
-    // There's a case where we can't just use x / note_width. For example, if
-    // your note_width is 3.1 you will have a rect starting at 3. When that
+    // There's a case where we can't just use x / m_note_width. For example, if
+    // your m_note_width is 3.1 you will have a rect starting at 3. When that
     // leftmost pixel of the rect is clicked you will do 3 / 3.1 which is 0
-    // and not 1. We can avoid that case by shifting x by 1 if note_width is
+    // and not 1. We can avoid that case by shifting x by 1 if m_note_width is
     // fractional, being careful not to shift out of bounds.
-    int x = event.x() - frame_thickness();
-    bool note_width_is_fractional = note_width - static_cast<int>(note_width) != 0;
+    int x = (event.x() + horizontal_scrollbar().value()) - frame_thickness();
+    bool note_width_is_fractional = m_note_width - static_cast<int>(m_note_width) != 0;
     bool x_is_not_last = x != widget_inner_rect().width() - 1;
     if (note_width_is_fractional && x_is_not_last)
         ++x;
-    x /= note_width;
+    x /= m_note_width;
 
-    m_audio_engine.set_roll_note(y, x, m_audio_engine.roll_note(y, x) == On ? Off : On);
+    int note = (note_count - 1) - y;
+    u32 on_sample = roll_length * (static_cast<double>(x) / m_num_notes);
+    u32 off_sample = (roll_length * (static_cast<double>(x + 1) / m_num_notes)) - 1;
+    m_audio_engine.set_roll_note(note, on_sample, off_sample);
 
     update();
 }
+
+// FIXME: Implement zoom and horizontal scroll events in LibGUI, not here.
+void RollWidget::mousewheel_event(GUI::MouseEvent& event)
+{
+    if (event.modifiers() & KeyModifier::Mod_Shift) {
+        horizontal_scrollbar().set_value(horizontal_scrollbar().value() + (event.wheel_delta() * horizontal_scroll_sensitivity));
+        return;
+    }
+
+    if (!(event.modifiers() & KeyModifier::Mod_Ctrl)) {
+        GUI::ScrollableWidget::mousewheel_event(event);
+        return;
+    }
+
+    double multiplier = event.wheel_delta() >= 0 ? 0.5 : 2;
+
+    if (m_zoom_level * multiplier > max_zoom)
+        return;
+
+    if (m_zoom_level * multiplier < 1) {
+        if (m_zoom_level == 1)
+            return;
+        m_zoom_level = 1;
+    } else {
+        m_zoom_level *= multiplier;
+    }
+
+    int absolute_x_of_pixel_at_cursor = horizontal_scrollbar().value() + event.position().x();
+    int absolute_x_of_pixel_at_cursor_after_resize = absolute_x_of_pixel_at_cursor * multiplier;
+    int new_scrollbar = absolute_x_of_pixel_at_cursor_after_resize - event.position().x();
+
+    m_roll_width = widget_inner_rect().width() * m_zoom_level;
+    set_content_size({ m_roll_width, roll_height });
+
+    horizontal_scrollbar().set_value(new_scrollbar);
+}