From ee143a6c38a411103b59d8f52b4efa7886c9289f Mon Sep 17 00:00:00 2001 From: fred Date: Sun, 24 Mar 2002 19:52:53 +0000 Subject: [PATCH] lilypond-0.1.1 --- Documentation/lilygut.pod | 89 ++++++++++++++++++--------------------- TODO | 68 ++++++++++++++++++++++-------- flower/choleski.cc | 66 ++++++++++++++++++++++++++--- make/lilypond.spec.in | 2 + 4 files changed, 151 insertions(+), 74 deletions(-) diff --git a/Documentation/lilygut.pod b/Documentation/lilygut.pod index 71d0f8f566..4d174f1e63 100644 --- a/Documentation/lilygut.pod +++ b/Documentation/lilygut.pod @@ -6,7 +6,8 @@ LilyGuts - doco to the internals of GNU LilyPond This page documents some aspects of the internals of GNU LilyPond. Some of this stuff comes from e-mail I wrote, some from e-mail others wrote, -some are large comments taken away from the headers +some are large comments taken away from the headers. This is why this +page may be a little incoherent. You should use doc++ to take a peek at the sources. @@ -28,20 +29,32 @@ might be integrated in larger systems. =item Parsing: -No difficult algorithms. Associated datastructures have prefix Input -(eg Input_score, Input_command). The .ly file is read, and converted -to +No difficult algorithms. The .ly file is read, and converted to a list +of C, which each contain C and paper/midi-definitions. =item Creating elements -Requests are processed and used to create elements (like balls, stems, -slurs etc). This is done by a hierarchy of "brokers" (called -Translators: the ones for paper output are Engravers, for MIDI -Performers), which swallow requests, broadcast them and couple -different elements. +The music is walked column by column. The iterators which do the +walking report the Request to Translators which use this information +to create elements, either MIDI or "visual" elements. The translators +form a hierarchy; the ones for paper output are Engravers, for MIDI +Performers). -In this step data-structures for the next steps are created and filled -with data: Score_elements, PScore, PCol. +The translators swallow requests, create elements, broadcast them to +other translators on higher or same level in the hierarchy: + +The stem of a voice A is broadcast to the staff which contains A, but +not to the noteheads of A, and not to the stems, beams and noteheads +of a different voice (say B) or a different staff. The stem and +noteheads of A are coupled, because the the Notehead_engraver +broadcasts its heads, and the Stem catches these. + +The engraver which agrees to handle a request decides whether to to +honor the request, ignore it, or merge it with other requests. Merging +of requests is preferably done with other requests done by members of +the same voicegroups (beams, brackets, stems). In this way you can put +the voices of 2 instruments in a conductor's score so they make chords +(the Stem_reqs of both instruments will be merged). =item Prebreaking @@ -50,35 +63,30 @@ Breakable stuff (eg. clefs and bars) are copied into pre and postbreaks. =item Preprocessing Some dependencies are resolved, such as the direction of stems, beams, +and "horizontal" placement issues (the order of clefs, keys etc, +placement of chords in multi-voice music), =item Break calculation: -The lines and horizontal positions of the columns are determined +The lines and horizontal positions of the columns are determined. =item Breaking - Through some magical interactions with Line_of_score and Super_elem (check out the source) the "lines" are produced. All other spanners can figure across which lines they are spread. If applicable, they break themselves into pieces. After this, each piece -works (or, if there are no pieces) the spanner throws out any -dependencies which are in the wrong line. +(or, if there are no pieces, the original spanner itself) throws out +any dependencies which are in the wrong line. =item Postprocesing: Some items and all spanners need computation after the PCol positions -are determined. +are determined. Examples: slurs, vertical positions of staffs. =item Output paper - -=item Output midi - -The music is run through a translator (called Performer) which -creates midi-items from the requests. - =back =head1 INTERNALS @@ -92,24 +100,7 @@ In music typesetting, the user might want to cram a lot more symbols on the paper than actually fits. To reflect this idea (the user asks more than we can do), the container for this data is called Request. -The music (requests) are read/interpreted by a set of objects -(translators), the Performers/Engravers. The engraver which agrees to -handle a request decides whether to to honor the request, ignore it, -or merge it with other requests. Merging of requests is preferably -done with other requests done by members of the same voicegroups -(beams, brackets, stems). - -The result of a request will be an C or a C, which -will be put on the score. - -Different staffs can produce different outputs; a melodious voice -which is put into a percussion-Staff, will be typeset as the rythm of -that voice. - -After C made up her mind, the resultant items and -spanners are put on the PScore. - -Some of the important requests are: +In a lot of other formats this would be called an 'Event' =over 4 @@ -205,8 +196,8 @@ this to the Staff_engraver. Staff_engraver will tell C about the C, which will add the C to the C it just created. -To decide on merging, C has grouped several -engravers. Please check F. +To decide on merging, several engravers have been grouped. Please +check F. =head1 ITEMS and SPANNERS @@ -228,8 +219,7 @@ should be calculated. =head1 BREAKING -So what's the deal with PREBREAK and POSTBREAK and all this -stuff? +So what is this PREBREAK and POSTBREAK stuff? Let's take text as an example. In German some compound words change their spelling if they are broken: "backen" becomes @@ -258,7 +248,7 @@ on the next line if it is broken. =head1 SPACING -I think my method is the most elegant algorithm i've seen so far. + Some terminology: I call a vertical group of symbols (notes) which start at the same time a "column". Each line of a score has notes in it, grouped in columns. The difference in starting time between those @@ -267,9 +257,9 @@ columns. Example: - time -----> + time -----> - col1 col2 col3 col4 + cols: col1 col2 col3 col4 voice1 1 1 @@ -284,8 +274,7 @@ Example: time_difference (col2 , col3) = 0.5 wholes, etc. -these differences are translated into ideal distances (these translations -have been the subject of discussion in this thread). +these differences are translated into ideal distances distance (col1,col2) = 10 pt distance (col1,col3) = 14.1 pt @@ -326,3 +315,5 @@ springs. This is an area that needs a lot of work, and the optimal solution to find is not of a mathematical nature. Gourlay's solution is used. + + diff --git a/TODO b/TODO index 78cecc175e..f617a2a566 100644 --- a/TODO +++ b/TODO @@ -6,6 +6,27 @@ done, or is an idea that I want to think about Most of the items are marked in the code as well, with full explanation. grep for TODO and ugh/ugr + * generate stuff in out/default, out/sun5-irix etc iso out/ +and out-sun5/ + + * derive dstream, texstream from ostream? + + * A typical pop-music example. + + * check libtool, automake + + * have make dist produce tarball in out/ directory. + + * write a faster Spring_spacer ( without matrices if possible ) + + * A decent scalar type + + * relate energybound to linelen unitspace fontsize etc. + + * naming of Voice_group/Voice + + * benchmark band_matrices. + * versioning stuff (cvt mudela, mudela, etc.) * get rid of gif files. @@ -23,6 +44,13 @@ grep for TODO and ugh/ugr * lyrics in chords still fuck up. * rewire acknowledge_element() logic with a process_acknowledged() + + * Global type registration. + + My_class * p = create_object( My_class ) + Type t = get_type ( *p ); + if ( t <= get_type( q )) + .. * progress when creating MIDI elts. @@ -32,16 +60,36 @@ grep for TODO and ugh/ugr * piano staff - * implement better breaking algorithm - * update 20 pt table * decent TeX page layout * a tutorial +3RD PARTY BUGS: + + * bugreport to doc++ devel: struct not in class hier; public + virtual baseclasses + + * DOC++ bugs/ newer version? + + * Rational infty(HUGE_VAL) on glibc / w32 + + * Fix profiling. gprof bugreport? + + * read from mmap directly: bugreport to flex developers-> + yy_scan_buffer in C++.. + + * (where are the) gcc compile warnings on linux + + PROJECTS + * input converters + - NIFF? + - ABC? + - SMDL? + * add to MIDI output: - tempo change - repeat @@ -134,16 +182,10 @@ PARSER BUGS - * fix mysterious Flex malloc bug - * should adjust stemlength for flag number. * lilypond - -> crash - * standchen triool beam up/down - - * (where are the) gcc compile warnings on linux - SEVERELY LACKING: * SPEED! @@ -214,11 +256,6 @@ SMALLISH PROJECTS * shared lib on Solaris too. - * bugreport to doc++ devel: struct not in class hier; public - virtual baseclasses - - * get rid of init_end; - * cleanup lily-proto.hh and proto.hh * half-sharps, half-flats @@ -250,9 +287,6 @@ SMALLISH PROJECTS * parshape - * read from mmap directly: bugreport to flex developers-> - yy_scan_buffer in C++.. - * binsearch/hash for identifiers * stafftypes: voice names/ instrument names. @@ -303,8 +337,6 @@ FUTURE * guitar chord - * better beamslope calculation: QLP for beams? - * Text_crescendo * clean solution for staffsize in items. diff --git a/flower/choleski.cc b/flower/choleski.cc index d619b97460..086759193f 100644 --- a/flower/choleski.cc +++ b/flower/choleski.cc @@ -12,13 +12,15 @@ const Real EPS = 1e-7; // so sue me. Hard coded // for testing new Matrix_storage. //#define PARANOID -Vector -Choleski_decomposition::solve(Vector rhs)const +void +Choleski_decomposition::full_matrix_solve(Vector &out, Vector const &rhs)const { int n= rhs.dim(); assert(n == L.dim()); - Vector y(n); - + Vector y; + y.set_dim( n); + out.set_dim(n); + // forward substitution for (int i=0; i < n; i++) { Real sum(0.0); @@ -26,18 +28,67 @@ Choleski_decomposition::solve(Vector rhs)const sum += y(j) * L(i,j); y(i) = (rhs(i) - sum)/L(i,i); } + for (int i=0; i < n; i++) y(i) /= D(i); // backward subst - Vector &x(rhs); // using input as return val. + Vector &x(out); // using input as return val. for (int i=n-1; i >= 0; i--) { Real sum(0.0); for (int j=i+1; j < n; j++) sum += L(j,i)*x(j); x(i) = (y(i) - sum)/L(i,i); } - return x; +} + +void +Choleski_decomposition::band_matrix_solve(Vector &out, Vector const &rhs)const +{ + int n= rhs.dim(); + int b = L.band_i(); + assert(n == L.dim()); + + out.set_dim(n); + + Vector y; + y.set_dim(n); + + // forward substitution + for (int i=0; i < n; i++) { + Real sum(0.0); + for (int j= 0 >? i - b; j < i; j++) + sum += y(j) * L(i,j); + y(i) = (rhs(i) - sum)/L(i,i); + } + for (int i=0; i < n; i++) + y(i) /= D(i); + + // backward subst + Vector &x(out); // using input as return val. + for (int i=n-1; i >= 0; i--) { + Real sum(0.0); + for (int j=i+1; j <= i + b&&j < n ; j++) + sum += L(j,i)*x(j); + x(i) = (y(i) - sum)/L(i,i); + } +} + +void +Choleski_decomposition::solve(Vector &x, Vector const &rhs)const +{ + if (L.band_b()) { + band_matrix_solve(x,rhs); + } else + full_matrix_solve(x,rhs); +} + +Vector +Choleski_decomposition::solve(Vector rhs)const +{ + Vector r; + solve(r, rhs); + return r; } void @@ -126,9 +177,10 @@ Choleski_decomposition::inverse() const int n=L.dim(); Matrix invm(n); Vector e_i(n); + Vector inv(n); for (int i = 0; i < n; i++) { e_i.set_unit(i); - Vector inv(solve(e_i)); + solve(inv, e_i); for (int j = 0 ; j