JS1k: The JavaScript code golfing competition

for(_="[j]~e~R=0;Qfor(PPLQL<On-N),JNL-1JIvalueH]=GGd[F+3FE+2FC4*(Be.A)}@,n%[L$n/2u[-y]'#fff''#000'n;](=ApageXX,YYc[c.;fc+1F[i],f);PiQi<i++)PyQy<;yBy*n+0,0%onmouse=B(Ny-1)*n+	><input type=r=Math.[j+h][y]=(e)=>$]=[];y]OL
PL in c)c$[0]+$[6]]GL;d.write`<pange H=9 id=xeset up=fyG%q()>`;g{{jQh=i;Pk=k>>=1;h>>=1)j=j<<1|h&1;j>i&&([R,e~G[e,R~]@Ph=1;2*h<=h*=2)+=2*h)Pj=i;j<i+h;jk=3.1Bj-i)/h,lcos(kJmsin(kJo=e*l+f*m,p=-e*m+f*l,e=R-o=f~-p,R+=o~+=p};q{T=gg%d=T.data;rsuPy=tQy<y{rs[
r=d[L)],sQg(r,s@vw{v=v[Ny]w=w[N
v=r$],w=s$];g(v,wu=u[N
uhypot(v,wJtmax(t,u@Slog(tO;LU=LJD=IK	LJM	I&&(d[UFUUCDFDDCKFKKCMFMM+2G[-L]/SJd[UEDEKEM+3GpgT%+9,0@=256%fyG120,120,16,16q(X=Y=bQa.down=a.move{Abuttons?(ldG+x.H+1,b=b||Awhich,lpGAaltKey?`square`:`round`,sSGb<3?:,lX,YJl+1Jc.stroke(Jq()):(baJ,b=0@;oncontextmenuApreventDefault()";G=/[^ #&-?DK-MS-}]/.exec(_);)with(_.split(G))_=join(shift());eval(_) <3

Zm9yKF89IltqXX5lflI9MDtRZm9yKFBQTFFMPE9uLU4pLEpOTC0xSkl2YWx1ZUhdPUdHZFtGKzNGRSsyRkM0KihCZS5BKX1ALG4lW0wkbi8yH3VbHy15XR4nI2ZmZicdJyMwMDAnHG47G10oGj1BcGFnZRlYGVgsWRlZGGNbYy4XOxdmYxYrMUYVW2ldFCxmEyk7ElBpUWk8G2kRKyspEFB5UXk8Hzt5EA9CeSpuKw4aMCwwJQxvbm1vdXNlCz1CKE55LTEpKm4rCT48aW5wdXQgdHlwZT1yCD1NYXRoLgdbaitoXQZbeV0FPShlEyk9PgQFJF0DPVtdOwJ5XQJPG0wQAVBMIGluIGMpYyRbMF0rJFs2XV1HTDtkLndyaXRlYDxwCGFuZ2UgSD05IGlkPXgIZXNldCALdXA9F2Z5RxwWDCUScSgpPmA7ZwR7ERB7alFoPWk7UGs9G2s+Pj0xO2g+Pj0xKWo9ajw8MXxoJjE7aj5pJiYoW1IsZRQTfhMUR1tlFCxSExQTfl1AUGg9MTsyKmg8PRtoKj0yKRErPTIqaClQaj1pO2o8aStoO2oQaz0zLjFCai1pKS9oLGwHY29zKGtKbQdzaW4oa0pvPWUGKmwrZgYqbSxwPS1lBiptK2YGKmwsZQY9Ui1vEwY9Zn4tcCxSKz1vE34rPXB9O3EEe1Q9F2dnDCUSZD1ULmRhdGE7cgJzAnUCUHk9dFF5PBt5EHtyBQJzWwFyAz1kWw5MKV0scwNRZyhyBSxzBUB2AncCD3t2BT12W055XQJ3BT13W04BdgM9ciRdBSx3Az1zJF0FO2codgUsdwUSdQU9dVtOAXUDB2h5cG90KHYDLHcDSnQHbWF4KHQsdQNAUwdsb2codBIPTx87TBBVPQ5MSkQ9DklLCUxKTQlJHiYmKGRbVUZVFVVDREZEFURDS0ZLFUtDTUZNFU0rMkceWx8tTF0vU0pkW1VFREVLRU0rM0cbF3BnGlQlKzksMEAWDD0yNTYlEhdmeUcdFhoxMjAsMTIwLDE2LDE2EnEoElg9WT1iUWEuC2Rvd249YS4LbW92ZQR7QWJ1dHRvbnM/KBdsZEcreC5IKzEsYj1ifHxBd2hpY2gsF2xwR0FhbHRLZXk/YHNxdWFyZWA6YHJvdW5kYCwXc1NHYjwzPx06HCwXbBpYLFlKF2waGCsxSmMuc3Ryb2tlKEpxKCkpOigXYmEaShgsYj0wQDtvbmNvbnRleHRtZW51BEFwcmV2ZW50RGVmYXVsdCgpIjtHPS9bXiAjJi0/REstTVMtfV0vLmV4ZWMoXyk7KXdpdGgoXy5zcGxpdChHKSlfPWpvaW4oc2hpZnQoKSk7ZXZhbChfKSA8Mw==

c = a.getContext`2d`;
d = document;
b = d.body;

// MiniFFT
// =======

// By xem
// With the great help of @BalintCsala, @Subzey and Kevin Kwok.

// This demo computes a 2D FFT of a 256 x 256px image, and plots it using a logarithmic scale.
// The user can use the mouse, keyboard and UI to edit the image.

// To compute a 2D FFT, we have to perform a 1D FFT on each line of the image,
// then consider the resulting 1D FFTs as a grid,
// and finally, perform a new 1D FFT every column of that grid.
// So, for a 256 x 256px image, 512 1D FFTs should be computed, in theory.
// In practice, all the FFTs are symmetrical, so it's possible to compute only a half of them and mirror the result.
// Mirroring the FFTs takes more code but makes the rendering much faster, which is needed in this demo.

// 256 is used many times in the demo, so we store it in N
N = 256;

// =======

// UI added below the canvas (a range input called x and a reset button).
// The reset button draws a black image and recomputes its FFT.
d.write`<p><input type=range value=9 id=x><input type=reset onmouseup=c.fillStyle='#000';c.fillRect(0,0,N,N);fft2d()>`;

// =======

// The miniFFT function computes a 1D FFT for a group of 2^N complex numbers.
// The arrays re represent the real parts and imaginary parts of these numbers.
// It's a JS port of the Cooley-Tukey radix-2 decimation-in-time algorithm.
// When this function is called on a line of pixels,
// re is the greyscale value of each pixel (values 0-255) and im is an array of zeros.
// This non-recursive implementation was optimized by Kevin Kwok.
// https://antimatter15.com/2015/05/cooley-tukey-fft-dct-idct-in-under-1k-of-javascript/
// We added ES6 destructuring and more intermediate vars to save bytes and gain time.
function miniFFT(re, im){
  for (i = 0; i < N; i++){
    for(j = 0, h = i, k = N; k >>= 1; h >>= 1){
      j = (j << 1) | (h & 1);
    }
    if (j > i){
      [re[j], re[i], im[j], im[i]] = [re[i], re[j], im[i], im[j]];
    }
  }
  for(hN = 1; hN * 2 <= N; hN *= 2){
    for (i = 0; i < N; i += hN * 2){
      for (j = i; j < i + hN; j++){
        pi = 3.14 * (j - i) / hN;
        cos = Math.cos(pi);
        sin = Math.sin(pi);
        tre =  re[j + hN] * cos + im[j+hN] * sin;
        tim = -re[j + hN] * sin + im[j+hN] * cos;
        re[j + hN] = re[j] - tre;
        im[j + hN] = im[j] - tim;
        re[j] += tre;
        im[j] += tim;
      }
    }
  }
}

// =======

// The fft2d function computes and draws the 2D FFT computation of the source image:

// Here's a schematic of the operations that are done for a 4 x 4px image.
// (the principle is applicable for any other power of 2).
// The pixels of each line are written as letters (A to P).
// The complex numbers contained in the 1D FFT of each line is written as a digit (re1 to re8, im1 to im8).
// The complex numbers contained in the 1D FFT of each column is written as a digit' (re1' to re4', im1' to im4')
// The pixels of the final image are written as a letter' (A' to D').
// Reminder: there are only 8 different complex numbers in the FFT of each line, and only 4 different FFT pixels due to symmetries.

// Original image
// -----------             
// | A B C D |
// | E F G H |
// | I J K L |
// | M N O P |
// -----------             

// Compute the 1D FFT of each line.

// miniFFT([A,B,C,D],[0,0,0,0]) = ([re1,re2,re2,re1],[im1,im2,im2,im1])
// miniFFT([E,F,G,H],[0,0,0,0]) = ([re3,re4,re4,re3],[im3,im4,im4,im3])
// miniFFT([I,J,K,L],[0,0,0,0]) = ([re5,re6,re6,re5],[im5,im6,im6,im4])
// miniFFT([M,N,O,P],[0,0,0,0]) = ([re7,re8,re8,re7],[im7,im8,im8,im7])

// Consider all the lines' 1D FFTs as a grid and compute the 1D FFT of each column.
 
// miniFFT([re1,re3,re5,re7],[im1,im3,im5,im7]) = ([re1',re3',re3',re1'],[re1',re3',re3',re1'])
// miniFFT([re2,re4,re6,re8],[im2,im4,im6,im8]) = ([re2',re4',re4',re2'],[re2',re4',re4',re2'])
// miniFFT([re2,re4,re6,re8],[im2,im4,im6,im8]) = ([re2',re4',re4',re2'],[re2',re4',re4',re2'])
// miniFFT([re1,re3,re5,re7],[im1,im3,im5,im7]) = ([re1',re3',re3',re1'],[re1',re3',re3',re1'])

// Consider all the columns' 1D FFTs as a grid and plot it with a logarithmic scale (because most values are very small or huge).

// -------------
// |A' B' B' A'|
// |C' D' D' C'|
// |C' D' D' C'|
// |A' B' B' A'|
// -------------

// And that's how we usually represent a 2D FFT.
// Note: plotting complex numbers as greyscale pixels implies a loss of information,
// so the resulting image can't be iFFT'd (inverse-FFT'd) back to the first image.
// That's why we didn't make the right side of the canvas drawable.

fft2d = function(){
  
  // Get the source image pixels.
  Z = c.getImageData(0, 0, N, N);
  d = Z.data;
  
  // Create three 256 x 256 2D arrays for real parts and imaginary parts and modulus of our complex numbers.
  re = [];
  im = [];
  fft = [];
  max = 0;
  
  // Call miniFFT on each line of the image.
  for(I = 0; I < N; I++){
    re[I] = [];
    im[I] = [];
    
    // Convert each pixel into a complex number.
    for(J = 0; J < N; J++){
    
      // Fill the real part with the pixels intensity (0 - 255).
      // (we only read the green intensity of the pixel. For greyscale images, R = G = B).
      re[I][J] = d[(I * N + J) * 4];
      
      // Fill the imaginary part with 0.
      im[I][J] = 0;
    }
    
    // Compute 1D FFT.
    miniFFT(re[I], im[I]);
  }
  
  // Create two 128 x 128 2D arrays to store the result of our vertical FFTs.
  // We'll compute only a half of the columns and then mirror the result.
  re2 = [];
  im2 = [];
  
  for(I = 0; I < N / 2; I++){
  
    re2[I] = re2[N - I] = [];
    im2[I] = im2[N - I] = [];
    
    for(J = 0; J < N; J++){
      
      // Fill the arrays with the columns of re and im.
      re2[I][J] = re[J][I];
      im2[I][J] = im[J][I];
    }
    
    // Call miniFFT on each column of re and im.
    miniFFT(re2[I], im2[I]);
      
    // Mirror the grid of complex numbers.
    fft[I] = fft[N - I] = [];
    
    for(J = 0; J < N; J++){
      
      // Compute the modulus of each complex number.
      // Math.hypot works fine because the modulus of a complex number is sqrt(re² + im²)
      fft[I][J] = Math.hypot(re2[I][J], im2[I][J]);
      
      // Remember the max value found.
      max = Math.max(max, fft[I][J]);
    }
  }
  
  // Compute the log of the max value.
  logmax = Math.log(max);
  
  // Draw each pixel of the 2D FFT divided by the log of the max value.
  // We draw the top-left quarter of the FFT and its four symmetries at the same time.
  for(I = 0; I < N / 2; I++){
  
    for(J = 0; J < N / 2; J++){
    
      t1 = (I * N + J) * 4;
      t2 = (I * N + N - J - 1) * 4;
      t3 = ((N - I - 1) * N + J) * 4;
      t4 = ((N - I - 1) * N + N - J - 1) * 4;
    
      if(fft[N / 2 - I])
      d[t1] = d[t1 + 1] = d[t1 + 2] = 
      d[t2] = d[t2 + 1] = d[t2 + 2] = 
      d[t3] = d[t3 + 1] = d[t3 + 2] = 
      d[t4] = d[t4 + 1] = d[t4 + 2] = 
      fft[N / 2 - I][N / 2 - J] / logmax;
      
      d[t1 + 3] =
      d[t2 + 3] =
      d[t3 + 3] =
      d[t4 + 3] =
      N;
    }
  }
  
  c.putImageData(Z, N + 9, 0);
  
}

// =======

// Built-in demo

// Draw a white square on a black background
c.fillRect(0, 0, N, N);
c.fillStyle = '#fff';
c.fillRect(120, 120, 16, 16);

// Compute its FFT
fft2d();

// =======

// Inputs

// Reset mouse coordinates (X, Y) and last mouse button pressed (F).
X = Y = F = 0;

// The goal here is to allow drawing with the left click or the right click pressed,
// using a single function, bound to onmousedown and onmousemove,
// without using onmouseup to stop drawing.
a.onmousedown = a.onmousemove = function(e, f){

  // First, test if one mouse button is pressed
  e.buttons
  
  // If a key button is pressed:
  ?
  
  (
    
    // Set line width to the value of the range input + 1
    // (because a line width of size 0 would draw nothing).
    c.lineWidth = +x.value + 1,
    
    // Remember the new mouse button number (F) if it's not set.
    F = F || e.which,
    
    // Press Alt to draw squares instead of rounds.
    c.lineCap = e.altKey ? `square` : `round`,
    
    // Left click: draw in white, right click: draw in black.
    c.strokeStyle = F < 3 ? '#fff' : '#000',
    
    // Draw a line from last saved X and Y to current X and Y + 1.
    // (if we don't add 1 to X or Y, the 0px line would not appear on the canvas).
    c.lineTo(X, Y),
    c.lineTo(X = e.pageX, Y = e.pageY + 1),
    
    // Trace the line.
    c.stroke(),
    
    // Compute the 2D FFT.
    fft2d()
  )
  
  // If no key button is pressed, nothing is drawn but:
  :
  (
    // Start a new path on the canvas.
    // This ensures that the next time a button is pressed, the line will be drawn on a new path,
    // and won't affect the previous paths in case of shape/size/color modification.
    c.beginPath(),
    
    // Save current X and Y.
    X = e.pageX,
    Y = e.pageY,
    
    // Reset F.
    F = 0
  )
};

// Disable context menu on right click, to allow drawing in black.
oncontextmenu = function(e, f){
  e.preventDefault()
}