let messages = Array();


function compileMicrocode() 
{ 
  let error = false;

  let spreadsheet = SpreadsheetApp.getActiveSpreadsheet();
  let sheet = spreadsheet.getSheetByName('Microcode');
  let headerRowLabels = sheet.getRange(1, 1, sheet.getFrozenRows(), 1);

  // Create a clean Compiler Message sheet
  let messagesSheet = spreadsheet.getSheetByName('Compiler Messages');
  if (messagesSheet == null)
  {
    messagesSheet = spreadsheet.insertSheet();
    messagesSheet.setName('Compiler Messages');
  }
  messagesSheet.clear();

  spreadsheet.setActiveSheet(sheet);

  // Find the Bit Width row
  let find = headerRowLabels.createTextFinder("Bit Width").matchEntireCell(true).matchCase(false).findAll();
  if (find.length != 1)
  {
    Browser.msgBox("Error: There must be one, and only one, frozen row where the first cell has 'Bit Width' in it.");
    error = true;
    return;
  }
  let bitWidthRow = find[0].getRow();
  let bitWidths = sheet.getRange(bitWidthRow, 2, 1, sheet.getLastColumn()).getValues()[0];
  // Trim non-numeric elements off the end
  while (typeof bitWidths[bitWidths.length - 1] != 'number') 
    bitWidths = bitWidths.slice(0, bitWidths.length - 1);

  let firstDataColumn = sheet.getFrozenColumns() + 1;

  let addressBitWidths = bitWidths.slice(0, sheet.getFrozenColumns() - 1);
  let dataBitWidths = bitWidths.slice(sheet.getFrozenColumns() - 1);

  // Count up the number of address and data bits
  let microcodeAddressBits = addressBitWidths.reduce((prev, curr) => prev + curr, 0);
  let microcodeBitWidth = dataBitWidths.reduce((prev, curr) => prev + curr, 0);

  // Find the Default values row.
  find = headerRowLabels.createTextFinder("Default value").matchEntireCell(true).matchCase(false).findAll();
  if (find.length != 1)
  {
    Browser.msgBox("Error: There must be one, and only one, frozen row where the first cell has 'Default value' in it.");
    error = true;
    return;
  }
  let defaultValuesRow = find[0].getRow();
  let defaultValues = sheet.getRange(defaultValuesRow, 2, 1, bitWidths.length + 1).getValues()[0];
  let addressDefaultValues = defaultValues.slice(0, sheet.getFrozenColumns() - 1);
  let dataDefaultValues = defaultValues.slice(sheet.getFrozenColumns() - 1, bitWidths.length);

  // Make sure there are some address bit columns
  if (microcodeAddressBits == 0)
  {
    Browser.msgBox("Error: There must be frozen columns, with the first column being an arbitrary label for the row, " +
      "and one or more columns defining the address bits, in MSB to LSB order.");
    error = true;
    return;
  }

  // Make sure there are some data bit columns
  if (dataBitWidths == 0)
  {
    Browser.msgBox("Error: There must be unfrozen columns defining the data bits, in LSB to MSB order.");
    error = true;
    return;
  }

  let romChipDataWidth = sheet.getParent().getRangeByName("ROMChipDataWidth").getValue().valueOf();

  let firstCompileRow = sheet.getFrozenRows(), lastCompileRow = sheet.getLastRow();
  let allValues = sheet.getSheetValues(1, 2, -1, -1);

  // Build the ROM
  let rom = Array(1 << microcodeAddressBits);
  // Go through every address in the ROM
  for (var addr = 0; addr < (1 << microcodeAddressBits) && !error; ++addr)
  {
    // Keep track of which row has written data to this address, so
    // we can detect if more than one row is writing
    let writtenByRow = -1;

    // Create an array for the data bits
    rom[addr] = Array(dataBitWidths.length);
    let strAddr = addr.toString(2);
    if (strAddr.length < microcodeAddressBits)
      strAddr = '0'.repeat(microcodeAddressBits - strAddr.length) + strAddr;

    // Go through all the rows, looking for addresses that match the current one
    for (let rowIndex = firstCompileRow; rowIndex < lastCompileRow; ++rowIndex)
    {
      let rowValues = allValues[rowIndex];

      // If all the cells with data are empty, this is a blank row. Skip it.
      if (rowValues.slice(0, bitWidths.length).reduce((prev, curr) => prev & (curr == ''), true) == true)
        continue;

      let rowAddressSpec = rowValues.slice(0, addressBitWidths.length);

      // If the row's address spec matches the current address we're compiling for
      if (addressMatch(rowIndex, strAddr, rowAddressSpec, addressDefaultValues, addressBitWidths))
      {
        // Check whether this address' bits have already been set by a different row
        if (writtenByRow == -1)
          writtenByRow = rowIndex;
        else
          logMessage('WARNING: address 0x' + addr.toString(16) + 
            ' is written to by row ' + (writtenByRow + 1) + 
            ' and by row ' + (rowIndex + 1));


        // Go through all the data values in the row
        for (let dataIndex = 0; dataIndex < dataBitWidths.length; ++dataIndex)
        {
          let data = rowValues[dataIndex + rowAddressSpec.length];
          // If the cell is empty, go to the next
          if (data === '')
            continue;
          // If the cell is a binary value, get it
          if (typeof data == 'string' && data[0] == 'b')
          {
            data = data.substring(1);
            if (!isBinary(data))
            {
              logMessage('ERROR: cell ' + columnLabel(dataIndex + firstDataColumn) +
               (rowIndex + 1) + ': value includes non-binary digits.');
              error = true;
              continue;
            }
            else if (data.length > dataBitWidths[dataIndex])
            {
              logMessage('ERROR: cell ' + columnLabel(dataIndex + firstDataColumn) + 
                (rowIndex + 1) + ': binary value is too wide.');
              error = true;
              continue;
            }
          }

          else if (typeof data == 'number')
          {
            if (data < 0 || data >= (1 << dataBitWidths[dataIndex]))
            {
              logMessage('ERROR: cell ' + columnLabel(dataIndex + firstDataColumn) +
               (rowIndex + 1) + ': value is out of range for the bit width.');
              error = true;
              continue;
            }
            data = data.toString(2);
          }

          else
          {
            logMessage('ERROR: cell ' + columnLabel(dataIndex + firstDataColumn) +
             (rowIndex + 1) + ': value is not a number.');
            error = true;
            continue;
          }

          // Write the data to the bit field
          let writeData = parseInt(data, 2);
          rom[addr][dataIndex] = writeData;
        }
      }
    }

    // If there are any data bits not set, set them to their default value
    for (let dataIndex = 0; dataIndex < dataDefaultValues.length; ++dataIndex)
    {
      if (rom[addr][dataIndex] === undefined)
        rom[addr][dataIndex] = dataDefaultValues[dataIndex];
    }
  }

  // Output the ROM to file(s)
  let chipsNeeded = Math.floor((microcodeBitWidth + romChipDataWidth - 1) / romChipDataWidth);
  let fileNamePattern = sheet.getParent().getRangeByName("OutputFileNamePattern").getValue().valueOf();
  let hash = fileNamePattern.search('#');
  // if we don't have a file name pattern that allows for a digit substitution
  if (hash == -1)
  {
    // Log an errror
    logMessage('ERROR: Output file name pattern does not have a "#" for putting the file number in.');
  }
  // Else (we have a good file name pattern)
  else
  {
    // Output the ROM files
    let fileType = sheet.getParent().getRangeByName("OutputFileType").getValue().valueOf();
    let intelHex = (fileType == 'Intel HEX');
    let verilogHex = (fileType == "Verilog readmemh");
    let hexFormat = intelHex || verilogHex;

    // First, build the hex text or binary blobs for each file
    // Go through each ROM address
    let outputData = Array(chipsNeeded);
    for (var i = 0; i < chipsNeeded; ++i)
    {
      if (hexFormat)
        outputData[i] = '';
      else
      {
        if (romChipDataWidth == 8)
          outputData[i] = new Uint8Array(1 << microcodeAddressBits);
        else if (romChipDataWidth == 16)
          outputData[i] = new Uint16Array(1 << microcodeAddressBits);
      }
    }
    let hexWordWidth = romChipDataWidth / 4;

    let checksums = Array(chipsNeeded);

    for (var addr = 0; addr < (1 << microcodeAddressBits) && !error; ++addr)
    {
      // Build a string of binary digits for this memory address' data
      let bits = '';
      for (let fieldIndex = 0; fieldIndex < rom[addr].length; ++fieldIndex)
      {
        bits += toRadix(rom[addr][fieldIndex], 2, dataBitWidths[fieldIndex]);
      }

      // If necessary, add trailing zero bits, so that we fill the data width of the chip
      let trailingZeroes = chipsNeeded * romChipDataWidth - bits.length;
      if (trailingZeroes > 0)
        bits += '0'.repeat(trailingZeroes);

      // Go through the binary digits, a ROM-chip-width at a time
      for (let chipIndex = 0, bitIndex = 0; chipIndex < chipsNeeded; chipIndex++, bitIndex += romChipDataWidth)
      {
        // Get the binary digits for the single memory location in a single ROM
        let chipData = bits.substring(bitIndex, bitIndex + romChipDataWidth);

        // If we're outputting hexadecimal text
        if (hexFormat)
        {
          // If this is the beginning of a line on an Intel Hex file, 
          if (intelHex && (addr & 0xf) == 0)
          {
            outputData[chipIndex] += ':10' + toRadix(addr, 16, 4) + '00';
            checksums[chipIndex] = 0x10 + ((addr / 256) & 0xff) + (addr & 0xff);
          }
          // Convert the bits to a hex value and add it to the output for this ROM
          let value = parseInt(chipData, 2);
          outputData[chipIndex] += toRadix(value, 16, hexWordWidth);
          // If this is a Verilog hex file, we need to insert a space
          if (verilogHex)
            outputData[chipIndex] += ' ';
            
          while (value)
          {
            checksums[chipIndex] += value & 0xff;
            value >>= 8;
          }
          // If this is the end of a line of 16 data bytes on an Intel Hex
          if ((addr & 0xf) == 0xf)
          {
            // For Intel hex files, write a checksum
            if (intelHex)
              outputData[chipIndex] += toRadix(-checksums[chipIndex] & 0xff, 16, 2);
            // For all files, write a newline
            outputData[chipIndex] += '\n';
          }
        }

        // Else (we're outputting binary data)
        else
        {
          outputData[chipIndex][addr] = parseInt(chipData, 2)
        }
      }
    }

    // Write the data out to files
    for (let chipIndex = 0; chipIndex < chipsNeeded; chipIndex++)
    {

      let fileName = fileNamePattern.substring(0, hash) + (chipIndex + 1) + fileNamePattern.substring(hash + 1);
      // If the output data is a Uint8Array, convert it to a string
      if (outputData[chipIndex] instanceof Uint8Array)
      {
        var blob = Utilities.newBlob(outputData[chipIndex]);
        blob.setName(fileName);
        try
        {
          // If the file already exists, update it
          let file = DriveApp.getFilesByName(fileName).next();
          let id = file.getId();
          Drive.Files.update(null, id, blob);
        }
        catch (e)
        {
          // If the file doesn't exist yet, create it.
          file = DriveApp.createFile(blob);
          file.setName(fileName);
        }
      }

      // Else (the output data is a string) write the string to a file
      else
      {
        try
        {
          // If the file already exists, update it
          let file = DriveApp.getFilesByName(fileName).next();
          file.setContent(outputData[chipIndex]);
        }
        catch (e)
        {
          // If the file doesn't exist yet, create it.
          DriveApp.createFile(fileName, outputData[chipIndex]);
        }
      }
    }
  }

  // Build a string with the required memory size
  let memSize = '';
  if (microcodeAddressBits < 10)
    memSize += 1 << microcodeAddressBits;
  else
    memSize += (1 << (microcodeAddressBits - 10)) + 'K';
  memSize += 'x' + romChipDataWidth;

  // Add in the number of ROM chips needed
  memSize += '; ' + chipsNeeded + ' chips.';

  if (error)
    logMessage('Compilation failed.');
  else
  {
    logMessage('Compilation complete.');
    logMessage('ROM required: ' + memSize);
  }

  // Write the messages to the sheet
  messagesSheet.getRange(1, 1, messages.length, 1).setValues(messages);

  spreadsheet.setActiveSheet(messagesSheet);
}

/////////////////////////////////////////////////////////////////
// Determine if an address (passed in as binary, in a string) matches the address specification
function addressMatch(rowNumber, strAddr, addrSpec, addrDefaultValues, bitWidths)
{
  let match = true, error = false;

  // Go through each field
  for (let field = bitWidths.length - 1; field >= 0 && match; --field)
  {
    // Get the address bits for this field
    let strFieldAddr = strAddr.substring(strAddr.length - bitWidths[field]);
    strAddr = strAddr.substring(0, strAddr.length - bitWidths[field]);

    let fieldSpec = addrSpec[field] !== '' ? addrSpec[field] : addrDefaultValues[field];

    // If the fieldSpec is a string
    if (typeof fieldSpec == 'string')
    {
      fieldSpec = fieldSpec.toLowerCase();
      // If the field spec is a "don't care", this field passes the check
      if (fieldSpec == 'x')
        continue;
      // If the spec is binary, toss the leading 'b' and make sure it's the right length
      if (fieldSpec[0] == 'b')
      {
        fieldSpec = fieldSpec.substring(1);
        let padding = bitWidths[field] - fieldSpec.length;
        if (padding > 0)
          fieldSpec = '0'.repeat(padding) + fieldSpec;
      }
    }

    // Else it's a number, convert it to binary
    else if (typeof fieldSpec == 'number')
      fieldSpec = toRadix(fieldSpec, 2, bitWidths[field]);

    // Else (not a string or number) flag an error
    else
      error = true;

    if (!error)
    {
      // If the length of spec and the address bit field are different, error
      if (fieldSpec.length != strFieldAddr.length)
        error = true;

      // Else (the lengths match)
      else
      {
        // Compare the spec to the address a character at a time
        for (let c = 0; c < fieldSpec.length; ++c)
        {
          // If the spec is 'x' (don't care) or if it matches the address, continue on to the next character
          if (fieldSpec[c] == 'x' || fieldSpec[c] == strFieldAddr[c])
            continue;
          // Else if the field spec has an invalid character, flag an error
          else if (fieldSpec[c] != '0' && fieldSpec[c] != '1')
          {
            error = true
            break;
          }
          // Else the match failed
          else
            match = false;
        }
      }
    }

    if (error)
    {
      logMessage('Error, row ' + rowNumber + ', column ' + (field + 1) + ': invalid value specification');
      match = false;
    }
  }

  return match;
}

//////////////////////////////////////////////////////////////////
// Ensure that all characters in the string are either 0 or 1
function isBinary(s)
{
  if (s.length == 0)
    return false;
  for (let i = 0; i < s.length; ++i)
  {
    if (s[i] != '0' && s[i] != '1')
      return false;
  }

  return true;
}

////////////////////////////////////////////////////////////////////
// Generate a column label, i.e. A..Z, AA..AZ, BA..BZ, etc
function columnLabel(index)
{
  let label = String.fromCharCode(64 + index % 26);
  if (index > 26)
    label = String.fromCharCode(64 + Math.floor(index / 26)) + label;
  return label;
}

////////////////////////////////////////////////////////////////////
// Convert a number to another radix, with leading zeroes as needed
function toRadix(value, radix, width)
{
  let result = value.toString(radix);
  let leadingZeroes = width - result.length;
  if (leadingZeroes > 0)
    result = '0'.repeat(leadingZeroes) + result;
  return result;
}

//////////////////////////////////////////////////////////////////
function logMessage(message)
{
  messages.push(Array(message));
}