#+TITLE: R-Line* IntroductionR-Line is a random line segment generator. Itproduces random values at regular rate, and thenlinearly interpolates between them. The algorithm hasaudio-rate parametric control of both the rangeand rate of change for generated values. This algorithm is a great little control signal generatorthat can add a bit of zest to an otherwisestatic parameter in a patch. It's a very efficient way toadd a warm organic feel to a patch.* Notable Implementation DetailsThis particular algorithm uses a fixed-point phasor similarto the ones seen in @!(ref "osc")!@ and @!(ref "fmpair")!@.Fixed point has very good numerical stability, which makesit ideal for a phasor algorithm. To keep things more portable, R-Line implements its ownpseudo-Random Number Generator (pRNG), using a commonalgorithm generating random values known as[[https://en.wikipedia.org/wiki/Linear_congruential_generator][Linear Congruential Generator]], or an LCG. This iswhat most =rand= functionimplementations use under the hood. The modulus, multiplier,and and increment values come from the MicrosoftVisual/Quick C/C++ library (as found on Wikipedia).* Tangled FilesR-Line tangles to a C file and a header file. The C file =rline.c= contains the core implementationcode. #+NAME: rline.c#+BEGIN_SRC c :tangle rline.c#include <math.h>#define SK_RLINE_PRIV#include "rline.h"<<macros>><<funcs>>#+END_SRC The header file =rline.h= contains forward functiondeclarations. When =SK_RLINE_PRIV= is enabled, the structsare exposed. Otherwise, they are left as opaque. #+NAME: rline.h#+BEGIN_SRC c :tangle rline.h#ifndef SK_RLINE_H#define SK_RLINE_H #ifndef SKFLT#define SKFLT float#endif <<typedefs>><<funcdefs>> #ifdef SK_RLINE_PRIV<<structs>>#endif#endif#+END_SRC* Core StructThe core struct is called =sk_rline=. #+NAME: typedefs#+BEGIN_SRC ctypedef struct sk_rline sk_rline;#+END_SRC #+NAME: structs#+BEGIN_SRC cstruct sk_rline {    <<sk_rline>>};#+END_SRC* Constants and VariablesThe value from the LCG is often scaled to be normalizedbetween 0 and 1. The constant required for this is$1/(2^31 - 1$, or =1/((1L<<31) - 1)=. This value isstored in a constant. #+NAME: sk_rline#+BEGIN_SRC cSKFLT rngscale;#+END_SRC #+NAME: set_random_scaler#+BEGIN_SRC crl->rngscale = 1.0 / ((1L<<31) - 1);#+END_SRC The current state of the random number generator is storedas an integer =rng=. It is initialized to be =seed=. #+NAME: sk_rline#+BEGIN_SRC cint rng;#+END_SRC #+NAME: init#+BEGIN_SRC crl->rng = seed;<<set_random_scaler>><<generate_initial_values>>#+END_SRC The fixed point phasor has two major constants: the maximumlength, as well as the masking value. Detailed explanationof these are beyond the scope of this document. For moreinformation, consult the relevant sections in@!(ref "osc")!@. #+NAME: macros#+BEGIN_SRC c#define SK_RLINE_PHSLEN 0x1000000L#define SK_RLINE_PHSMSK 0xFFFFFFL#+END_SRC The variable =maxlens= is maximum phasor length converted tounits of seconds by dviding it by the sampling rate.Multipyling this value with a frequency will return anincrement value in units of phasor, which is usedas the phasor increment value. #+NAME: sk_rline#+BEGIN_SRC cSKFLT maxlens;#+END_SRC #+NAME: init#+BEGIN_SRC crl->maxlens = (SKFLT)SK_RLINE_PHSLEN / sr;#+END_SRC Phase position is stored in an unsigned long called=phspos=. When it needs to be converted for use in floatingpoint operations , the constant =scale= is used. #+NAME: sk_rline#+BEGIN_SRC cunsigned long phasepos;SKFLT scale;#+END_SRC #+NAME: init#+BEGIN_SRC crl->phasepos = 0;#+END_SRC The scale value works by normalizing to be in the range 0-1by dividing by the max phase length =SK_RLINE_PHSLEN=, thenscaling it to be the difference between the start/end pointvalues. Doing this shaves off a divide operation later. #+NAME: calculate_initial_scale#+BEGIN_SRC crl->scale = (rl->end - rl->start) / SK_RLINE_PHSLEN;#+END_SRC A line has two points: a start point, and an end point.These are stored as normalized floating point variables=start= and =end=, and then are dynamically scaled to the=min= and =max= values during computation. #+NAME: sk_rline#+BEGIN_SRC cSKFLT start;SKFLT end;#+END_SRC #+NAME: generate_initial_values#+BEGIN_SRC crl->rng = LCG(rl->rng);rl->start = RNG(rl->rng) * rl->rngscale;rl->rng = LCG(rl->rng);rl->end = RNG(rl->rng) * rl->rngscale;<<calculate_initial_scale>>#+END_SRC* Linear Congruential GeneratorAn internal[[https://en.wikipedia.org/wiki/Linear_congruential_generator][Linear Congruential Generator]] isused to generate sequences of pseudo-random numbers. It is the following equation $$y(n) = ((y(n - 1) * a + c) \gg 1)\& m$$ Where $m$ is the masking value =0x7ffffff=, $a$ is a=multiplier=, and $c$ is the =increment=. In thisimplementation, $a$ will be =0x343fd=, and $c$ will be=0x2693ec3=. These constants come from the wikipedia pageon LCGs, and originate the Microsoft Visual C/C++ standardlibrary. The LCG here can be implemented as a stateless function ormacro. In this case, we will go with the macro. #+NAME: macros#+BEGIN_SRC c#define LCG(y) (y * 0x343fd + 0x269ec3)#+END_SRC The =LCG= operation only computes the next state state ofthe random-number generator. To actually get it within thecorrect bounds for this sytem, it has to be right-shiftedto knock it down 1 bit, then masked by =0x7ffffff= as a kindof modulo operation. This macro operation =RNG= assumes that =y= is the currentstate of the LCG.#+NAME: macros#+BEGIN_SRC c#define RNG(y) ((y >> 1) & 0x7fffffff)#+END_SRC* InitializationInitialization is done with =sk_rline_init=. The main things needed for initialization are the samplingrate =sr=, as well as the initial seed value for the randomnumber generator. #+NAME: funcdefs#+BEGIN_SRC cvoid sk_rline_init(sk_rline *rl, int sr, int seed);#+END_SRC #+NAME: funcs#+BEGIN_SRC cvoid sk_rline_init(sk_rline *rl, int sr, int seed){    <<init>>}#+END_SRC* Parameters** Minimum valueSet with =sk_rline_min=. #+NAME: funcdefs#+BEGIN_SRC cvoid sk_rline_min(sk_rline *rl, SKFLT min);#+END_SRC #+NAME: funcs#+BEGIN_SRC cvoid sk_rline_min(sk_rline *rl, SKFLT min){    rl->min = min;}#+END_SRC #+NAME: sk_rline#+BEGIN_SRC cSKFLT min;#+END_SRC Initialized to be 0. #+NAME: init#+BEGIN_SRC csk_rline_min(rl, 0);#+END_SRC** Maximum valueSet with =sk_rline_max=. #+NAME: funcdefs#+BEGIN_SRC cvoid sk_rline_max(sk_rline *rl, SKFLT max);#+END_SRC #+NAME: funcs#+BEGIN_SRC cvoid sk_rline_max(sk_rline *rl, SKFLT max){    rl->max= max;}#+END_SRC #+NAME: sk_rline#+BEGIN_SRC cSKFLT max;#+END_SRC Initialized to be 1. #+NAME: init#+BEGIN_SRC csk_rline_max(rl, 1);#+END_SRC** RateSet with =sk_rline_rate=. #+NAME: funcdefs#+BEGIN_SRC cvoid sk_rline_rate(sk_rline *rl, SKFLT rate);#+END_SRC #+NAME: funcs#+BEGIN_SRC cvoid sk_rline_rate(sk_rline *rl, SKFLT rate){    rl->rate= rate;}#+END_SRC #+NAME: sk_rline#+BEGIN_SRC cSKFLT rate;#+END_SRC Initialized to be an arbitrary default value 1. #+NAME: init#+BEGIN_SRC csk_rline_rate(rl, 1);#+END_SRC* Computing a sampleA single sample is computed with =sk_rline_tick=. #+NAME: funcdefs#+BEGIN_SRC cSKFLT sk_rline_tick(sk_rline *rl);#+END_SRC #+NAME: funcs#+BEGIN_SRC cSKFLT sk_rline_tick(sk_rline *rl){    SKFLT out;     out = 0;     <<compute_current_sample>>    <<update_phase>>    <<generate_next_line_segment>>     return out;}#+END_SRC Compute the current sample. The line interpolation iscalculated in a normalized space, then scaled to bein the min/max range. Doing it this way allows the min/maxvalues to be dynamically changed over time without havingto wait for the next line. The normalized output can be computed with the expression: $$y = x_1 + pc$$ Where $x_1$ is the starting point of the line, $p$ isthe current phase increment, represented in fixed point, and$c$ is the constant that normalizes and scales the phase tobe the amount of progress to value $x_2$. #+NAME: compute_current_sample#+BEGIN_SRC cout = rl->start + rl->phasepos*rl->scale;out = out * (rl->max - rl->min) + rl->min;#+END_SRC  Update phase position. The phase is updated by incrementingit by a amount obtained by multiplying the frequency by themaximum phase length in units of seconds. How this works isbeyond the scope of this document, but is explained in @!(ref"osc")!@. #+NAME: update_phase#+BEGIN_SRC crl->phasepos += floor(rl->rate * rl->maxlens);#+END_SRC Generate next line segment. Preparation for a new linesegment happens when the phase of the phasor reaches theend, and is greater than or equal to the max length.The phasor is masked in order to filter out upperbits and allow the lower bits to roll over. The the startingvalue is set to be the current end value, and a new endvalue is obtained using the random number generator. After the new points have been obtained, the constant usedto normalize + scale the phasor value is computed. Dividingby the maximum phasor length normalizes the phasor to be inrange 0 and 1. Multiplying by the difference of the twosegment values scales this value to be in the correct range.This constant is useful because it shaves off a divideoperation, which has traditionally been a costly arithmeticcomputatoin compared to a multiply. #+NAME: generate_next_line_segment#+BEGIN_SRC cif (rl->phasepos >= SK_RLINE_PHSLEN) {    rl->phasepos &= SK_RLINE_PHSMSK;    rl->start = rl->end;    rl->rng = LCG(rl->rng);    rl->end = RNG(rl->rng) * rl->rngscale;    rl->scale = (rl->end - rl->start) / SK_RLINE_PHSLEN;}#+END_SRC