// Copyright 2005-8 Ben Hutchings <ben@decadent.org.uk>.
// See the file "COPYING" for licence details.

#include <cerrno>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <ostream>
#include <sstream>
#include <stdexcept>

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

#include <gdkmm/pixbuf.h>
#include <glibmm/miscutils.h>
#include <glibmm/spawn.h>

#include "dvd.hpp"
#include "generate_dvd.hpp"
#include "xml_utils.hpp"

namespace
{
    // Return a closeness metric of an "end" rectangle to a "start"
    // rectangle in the upward (-1) or downward (+1) direction.  Given
    // several possible "end" rectangles, the one that seems visually
    // closest in the given direction should have the highest value of
    // this metric.  This is necessarily a heuristic function!    
    double directed_closeness(const rectangle & start, const rectangle & end,
			      int y_dir)
    {
	// The obvious approach is to use the centres of the
	// rectangles.  However, for the "end" rectangle, using the
	// horizontal position nearest the centre of the "start"
	// rectangle seems to produce more reasonable results.  For
	// example, if there are two "end" rectangles equally near to
	// the "start" rectangle in terms of vertical distance and one
	// of them horizontally overlaps the centre of the "start"
	// rectangle, we want to pick that one even if the centre of
	// that rectangle is further away from the centre of the
	// "start" rectangle.
	int start_x = (start.left + start.right) / 2;
	int start_y = (start.top + start.bottom) / 2;
	int end_y = (end.top + end.bottom) / 2;
	int end_x;
	if (end.right < start_x)
	    end_x = end.right;
	else if (end.left > start_x)
	    end_x = end.left;
	else
	    end_x = start_x;

	// Return cosine of angle between the line between these points
	// and the vertical, divided by the distance between the points
	// if that is defined and positive; otherwise return 0.
	int vertical_distance = (end_y - start_y) * y_dir;
	if (vertical_distance <= 0)
	    return 0.0;
	double distance_squared =
	    (end_x - start_x) * (end_x - start_x)
	    + (end_y - start_y) * (end_y - start_y);
	return vertical_distance / distance_squared;
    }

    std::string temp_file_name(const temp_dir & dir,
			       std::string base_name,
			       unsigned index=0)
    {
	if (index != 0)
	{
	    std::size_t index_pos = base_name.find("%3d");
	    assert(index_pos != std::string::npos);
	    base_name[index_pos] = '0' + index / 100;
	    base_name[index_pos + 1] = '0' + (index / 10) % 10;
	    base_name[index_pos + 2] = '0' + index % 10;
	}

	return Glib::build_filename(dir.get_name(), base_name);
    }

    // We would like to use just a single frame for the menu but this
    // seems not to be legal or compatible.  The minimum length of a
    // cell is 0.4 seconds but I've seen a static menu using 12 frames
    // on a commercial "PAL" disc so let's use 12 frames regardless.
    unsigned menu_duration_frames(const video::frame_params & params)
    {
	return 12;
    }
    double menu_duration_seconds(const video::frame_params & params)
    {
	return double(menu_duration_frames(params))
	    / double(params.rate_numer)
	    * double(params.rate_denom);
    }

    void throw_length_error(const char * limit_type, std::size_t limit)
    {
	std::ostringstream oss;
	oss << "exceeded DVD limit: " << limit_type << " > " << limit;
	throw std::length_error(oss.str());
    }

    // dvdauthor uses some menu numbers to represent entry points -
    // distinct from the actual numbers of the menus assigned as those
    // entry points - resulting in a practical limit of 119 per
    // domain.  This seems to be an oddity of the parser that could be
    // fixed, but for now we'll have to work with it.
    const unsigned dvdauthor_anonymous_menus_max = dvd::domain_pgcs_max - 8;

    // The current navigation code packs menu and button number into a
    // single register, so the number of menus is limited to
    // dvd::reg_s8_button_mult - 1 == 1023.  However temp_file_name()
    // is limited to 999 numbered files and it seems pointless to
    // change it to get another 24.
    // If people really need more we could use separate menu and
    // button number registers, possibly allowing up to 11900 menus
    // (the size of the indirect jump tables might become a problem
    // though).
    const unsigned menus_max = 999;
}

dvd_generator::dvd_generator(const video::frame_params & frame_params,
			     mpeg_encoder encoder)
	: temp_dir_("videolink-"),
	  frame_params_(frame_params),
	  encoder_(encoder)
{}

dvd_generator::pgc_ref dvd_generator::add_menu()
{
    pgc_ref next_menu(menu_pgc, menus_.size());

    if (next_menu.index == menus_max)
	throw_length_error("number of menus", menus_max);

    menus_.resize(next_menu.index + 1);
    return next_menu;
}

void dvd_generator::add_menu_entry(unsigned index,
				   const rectangle & area,
				   const pgc_ref & target)
{
    assert(index < menus_.size());
    assert(target.type == menu_pgc && target.index < menus_.size()
	   || target.type == title_pgc && target.index < titles_.size());

    if (menus_[index].entries.size() == dvd::menu_buttons_max)
	throw_length_error("number of buttons", dvd::menu_buttons_max);

    menu_entry new_entry = { area, target };
    menus_[index].entries.push_back(new_entry);
}

void dvd_generator::generate_menu_vob(unsigned index,
				      Glib::RefPtr<Gdk::Pixbuf> background,
				      Glib::RefPtr<Gdk::Pixbuf> highlights)
    const
{
    assert(index < menus_.size());
    const menu & this_menu = menus_[index];

    std::string background_name(
	temp_file_name(temp_dir_, "menu-%3d-back.png", 1 + index));
    std::cout << "INFO: Saving " << background_name << std::endl;
    background->save(background_name, "png");

    std::string highlights_name(
	temp_file_name(temp_dir_, "menu-%3d-links.png", 1 + index));
    std::cout << "INFO: Saving " << highlights_name << std::endl;
    highlights->save(highlights_name, "png");

    std::string spumux_name(
	temp_file_name(temp_dir_, "menu-%3d.subpictures", 1 + index));
    std::ofstream spumux_file(spumux_name.c_str());
    spumux_file <<
	"<subpictures>\n"
	"  <stream>\n"
	"    <spu force='yes' start='00:00:00.00'\n"
	"        highlight='" << highlights_name << "'\n"
	"        select='" << highlights_name << "'>\n";
    int button_count = this_menu.entries.size();
    for (int i = 0; i != button_count; ++i)
    {
	const menu_entry & this_entry = this_menu.entries[i];

	// We program left and right to cycle through the buttons in
	// the order the entries were added.  This should result in
	// left and right behaving like the tab and shift-tab keys
	// would in the browser.  Hopefully that's a sensible order.
	// We program up and down to behave geometrically.
	int up_button = i, down_button = i;
	double up_closeness = 0.0, down_closeness = 0.0;
	for (int j = 0; j != button_count; ++j)
	{
	    const menu_entry & other_entry = this_menu.entries[j];
	    double closeness = directed_closeness(
		this_entry.area, other_entry.area, -1);
	    if (closeness > up_closeness)
	    {
		up_button = j;
		up_closeness = closeness;
	    }
	    else
	    {
		closeness = directed_closeness(
		    this_entry.area, other_entry.area, 1);
		if (closeness > down_closeness)
		{
		    down_button = j;
		    down_closeness = closeness;
		}
	    }
	}
	// Pad vertically to even y coordinates since dvdauthor claims
	// odd values may result in incorrect display.
	// XXX This may cause overlappping where it wasn't previously
	// a problem.
	spumux_file << "      <button"
	    " x0='" << this_entry.area.left << "'"
	    " y0='" << (this_entry.area.top & ~1) << "'"
	    " x1='" << this_entry.area.right << "'"
	    " y1='" << ((this_entry.area.bottom + 1) & ~1) << "'"
	    " left='" << (i == 0 ? button_count : i) << "'"
	    " right='" << 1 + (i + 1) % button_count << "'"
	    " up='" << 1 + up_button << "'"
	    " down='" << 1 + down_button << "'"
	    "/>\n";
    }
    spumux_file <<
	"    </spu>\n"
	"  </stream>\n"
	"</subpictures>\n";
    spumux_file.close();
    if (!spumux_file)
	throw std::runtime_error("Failed to write control file for spumux");

    std::string output_name(
	temp_file_name(temp_dir_, "menu-%3d.mpeg", 1 + index));

    std::ostringstream command_stream;
    if (encoder_ == mpeg_encoder_ffmpeg)
    {
	command_stream <<
	    "ffmpeg -f image2 -vcodec png"
	    " -r " << frame_params_.rate_numer <<
	    "/" << frame_params_.rate_denom <<
	    " -loop_input -i " << background_name <<
	    " -t " << menu_duration_seconds(frame_params_) <<
	    " -target " << frame_params_.common_name <<  "-dvd"
	    " -vcodec mpeg2video -aspect 4:3 -an -y /dev/stdout";
    }
    else
    {
	assert(encoder_ == mpeg_encoder_mjpegtools);
	command_stream
	    << "pngtopnm " << background_name
	    << " | ppmtoy4m -v0 -n" << menu_duration_frames(frame_params_)
	    << " -F" << frame_params_.rate_numer << ":" << frame_params_.rate_denom
	    << " -A" << frame_params_.pixel_ratio_width
	    << ":" << frame_params_.pixel_ratio_height
	    << " -Ip -S420mpeg2"
	    " | mpeg2enc -v0 -f8 -a2 -o/dev/stdout"
	    " | mplex -v0 -f8 -o/dev/stdout /dev/stdin";
    }
    command_stream
	<< " | spumux -v0 -mdvd " << spumux_name << " > " << output_name;
    std::string command(command_stream.str());
    const char * argv[] = {
	"/bin/sh", "-c", command.c_str(), 0
    };
    std::cout << "INFO: Running " << command << std::endl;
    int command_result;
    Glib::spawn_sync(".",
		     Glib::ArrayHandle<std::string>(
			 argv, sizeof(argv)/sizeof(argv[0]),
			 Glib::OWNERSHIP_NONE),
		     Glib::SPAWN_STDOUT_TO_DEV_NULL,
		     sigc::slot<void>(),
		     0, 0,
		     &command_result);
    struct stat stat_buf;
    if (command_result != 0 || stat(output_name.c_str(), &stat_buf) != 0
	|| stat_buf.st_size == 0)
	throw std::runtime_error("spumux pipeline failed");
}

dvd_generator::pgc_ref dvd_generator::add_title(vob_list & content)
{
    pgc_ref next_title(title_pgc, titles_.size());

    // Check against maximum number of titles.
    if (next_title.index == dvd::titles_max)
	throw_length_error("number of titles", dvd::titles_max);

    titles_.resize(next_title.index + 1);
    titles_[next_title.index].swap(content);
    return next_title;
}

void dvd_generator::generate(const std::string & output_dir) const
{
    // This function uses a mixture of 0-based and 1-based numbering,
    // due to the differing conventions of the language and the DVD
    // format.  Variable names ending in "_index" indicate 0-based
    // indices and variable names ending in "_num" indicate 1-based
    // numbers.

    std::string name(temp_file_name(temp_dir_, "videolink.dvdauthor"));
    std::ofstream file(name.c_str());
    file << "<dvdauthor>\n";

    // We generate code that uses registers in the following way:
    //
    // g0: Scratch.
    // g1: Target location when jumping between menus.  Top 6 bits are
    //     the button number (like s8) and bottom 10 bits are the menu
    //     number.  This is used for selecting the appropriate button
    //     when entering a menu, for completing indirect jumps between
    //     domains, and for jumping to the correct menu after exiting a
    //     title.  This is set to 0 in the pre-routine of the target
    //     menu.
    // g2: Current location in menus.  This is used for jumping to the
    //     correct menu when the player exits a title.
    // g3: Target chapter number plus 1 when jumping to a title.
    //     This is used to jump to the correct chapter and to
    //     distinguish between indirect jumps to menus and titles.
    //     This is set to 0 in the pre-routine of the target title.
    // g4: Source menu location used to jump to a title.  This is
    //     compared with g2 to determine whether to increment the
    //     button number if the title is played to the end.

    static const unsigned button_mult = dvd::reg_s8_button_mult;
    static const unsigned menu_mask = button_mult - 1;
    static const unsigned button_mask = (1U << dvd::reg_bits) - button_mult;

    // Iterate over VMGM and titlesets.  For these purposes, we
    // consider the VMGM to be titleset 0.

    // We need a titleset for each title, and we may also need titlesets to
    // hold extra menus if we have too many for the VMGM.
    // Also, we need at least one titleset.
    const unsigned titleset_end = std::max<unsigned>(
	    1U + std::max<unsigned>(1U, titles_.size()),
	    (menus_.size() + dvdauthor_anonymous_menus_max - 1)
		 / dvdauthor_anonymous_menus_max);

    for (unsigned titleset_num = 0;
	 titleset_num != titleset_end;
	 ++titleset_num)
    {
	const char * const outer_element_name =
	    titleset_num == 0 ? "vmgm" : "titleset";
	const bool have_real_title =
	    titleset_num != 0 && titleset_num <= titles_.size();
	const bool have_real_menus =
	    titleset_num * dvdauthor_anonymous_menus_max < menus_.size();

	file << "  <" << outer_element_name << ">\n"
	     << "    <menus>\n";

	const unsigned menu_begin = titleset_num * dvdauthor_anonymous_menus_max;
	const unsigned menu_end =
	    have_real_menus
	    ? std::min<unsigned>(
		(titleset_num + 1) * dvdauthor_anonymous_menus_max,
		menus_.size())
	    : menu_begin + 1;

	for (unsigned menu_index = menu_begin;
	     menu_index != menu_end;
	     ++menu_index)
	{
	    // There are various cases in which menus may be called:
	    //
	    // 1. The user follows a direct link to the menu.
	    // 2. The user follows an indirect link to some other menu
	    //    and that goes via this menu.  This is distinguished
            //    from case 1 by the value of g1.  We must jump to or
	    //    at least toward the other menu.
	    // 3. The title menu is called when the disc is first
	    //    played or the user presses the "top menu" button.
	    //    This is distinguished from cases 2 and 3 by g1 == 0.
	    //    We make this look like case 1.
	    // 4. The root menu of a titleset is called when the user
	    //    follows an indirect link to the title.  This is
	    //    distinguished from all other cases by g3 != 0.  We
	    //    must jump to the title.
	    // 5. The root menu of a titleset is called when the title
	    //    ends or the user presses the "menu" button during
	    //    the title.  This is distinguished from cases 1, 2
	    //    and 4 by g1 == 0 and g3 == 0.  We must jump to the
	    //    latest menu (which can turn into case 1 or 2).
	    //
	    // Cases 3 and 5 do not apply to the same menus so they
	    // do not need to be distinguished.

	    if (menu_index == 0)
	    {
		// Title menu.
		file <<
		    "      <pgc entry='title'>\n"
		    "        <pre>\n"
		    "          if (g1 eq 0)\n" // case 3
		    "            g1 = " << 1 + button_mult << ";\n";
	    }
	    else if (menu_index == titleset_num * dvdauthor_anonymous_menus_max)
	    {
		// Root menu.
 		file <<
		    "      <pgc entry='root'>\n"
		    "        <pre>\n";
		if (have_real_title)
		{
		    file <<
			"          if (g3 ne 0)\n" // case 4
			"            jump title 1;\n"
			"          if (g1 eq 0) {\n" // case 5
			"            g1 = g2;\n"
			"            jump vmgm menu entry title;\n"
			"          }\n";
		}
	    }
	    else
	    {
		// Some other menu.
		file <<
		    "      <pgc>\n"
		    "        <pre>\n";
	    }

	    if (!have_real_menus)
	    {
		// This is a root menu only reachable from the title.
		file <<
		    "        </pre>\n"
		    "      </pgc>\n";
		continue;
	    }

	    const menu & this_menu = menus_[menu_index];

	    // Detect and handle case 2.
	    //
	    // There is a limit of 128 VM instructions in each PGC.
	    // Also, we can't jump to an arbitrary menu in another
	    // domain.  Finally, we can't do computed jumps.
	    // Therefore we statically expand and distribute a binary
	    // search across the menus, resulting in a code size of
	    // O(log(menu_count)) in each menu.  In practice there are
	    // at most 11 conditional jumps needed in any menu.
	    //
	    // The initial bounds of the binary search are strange
	    // because we must ensure that any jump between titlesets
	    // is to the first menu of the titleset, marked as the
	    // root entry.

	    // Mask target location to get the target menu.
	    file << "          g0 = g1 &amp; " << menu_mask << ";\n";

	    for (unsigned
		     bottom = 0,
		     top = 16 * dvdauthor_anonymous_menus_max;
		 top - bottom > 1;)
	    {
		unsigned middle = (bottom + top) / 2;
		if (menu_index == bottom && middle < menus_.size())
		{
		    file << "          if (g0 ge " << 1 + middle << ")\n"
			 << "            jump ";
		    unsigned target_titleset_num =
			middle / dvdauthor_anonymous_menus_max;
		    if (target_titleset_num != titleset_num)
		    {
			assert(middle % dvdauthor_anonymous_menus_max == 0);
			file << "titleset " << target_titleset_num
			     << " menu entry root";
		    }
		    else
		    {
			file << "menu "
			     << 1 + middle % dvdauthor_anonymous_menus_max;
		    }
		    file << ";\n";
		}
		if (menu_index >= middle)
		    bottom = middle;
		else
		    top = middle;
	    }

	    // Case 1.

	    // Highlight the appropriate button.
	    file << "          s8 = g1 &amp; " << button_mask << ";\n";

	    // Copy the target location to the current location and
	    // then clear the target location so that the title menu
	    // can distinguish cases 2 and 3.
	    file <<
		"          g2 = g1;\n"
		"          g1 = 0;\n";

	    file <<
		"        </pre>\n"
		"        <vob file='"
		 << temp_file_name(temp_dir_, "menu-%3d.mpeg",
				   1 + menu_index)
		 << "'>\n"
		// Define a cell covering the whole menu and set a still
		// time at the end of that, since it seems all players
		// support that but some ignore a still time set on a PGC.
		"          <cell start='0' end='"
		 << std::fixed << std::setprecision(4)
		 << menu_duration_seconds(frame_params_) << "'"
		" chapter='yes' pause='inf'/>\n"
		"        </vob>\n";

	    for (unsigned button_index = 0;
		 button_index != this_menu.entries.size();
		 ++button_index)
	    {
		const pgc_ref & target =
		    this_menu.entries[button_index].target;

		file << "        <button> ";

		if (target.type == menu_pgc)
		{
		    unsigned target_button_num;

		    if (target.sub_index)
		    {
			target_button_num = target.sub_index;
		    }
		    else
		    {
			// Look for a button on the new menu that links
			// back to this one.  If there is one, set that to
			// be the highlighted button; otherwise, use the
			// first button.
			const std::vector<menu_entry> & target_menu_entries =
			    menus_[target.index].entries;
			pgc_ref this_pgc(menu_pgc, menu_index);
			target_button_num = target_menu_entries.size();
			while (target_button_num != 1
			       && (target_menu_entries[target_button_num - 1].target
				   != this_pgc))
			    --target_button_num;
		    }
			 
		    // Set new menu location.
		    file << "g1 = "
			 << (1 + target.index + target_button_num * button_mult)
			 << "; ";
		    // Jump to the target menu.
		    unsigned target_titleset_num =
			target.index / dvdauthor_anonymous_menus_max;
		    if (target_titleset_num == titleset_num)
			file << "jump menu "
			     << 1 + (target.index
				     % dvdauthor_anonymous_menus_max)
			     << "; ";
		    else if (target_titleset_num == 0)
			file << "jump vmgm menu entry title; ";
		    else
			file << "jump titleset " << target_titleset_num
			     << " menu entry root; ";
		}
		else
		{
		    assert(target.type == title_pgc);

		    // Record current menu location and set target chapter
		    // number.
		    file <<
			"g2 = " << (1 + menu_index
				    + (1 + button_index) * button_mult) << "; "
			"g3 = " << 1 + target.sub_index << "; ";
		    // Jump to the target title, possibly via its titleset's
		    // root menu.
		    unsigned target_titleset_num = 1 + target.index;
		    if (titleset_num == 0)
			file << "jump title " << target_titleset_num << "; ";
		    else if (target_titleset_num == titleset_num)
			file << "jump title 1; ";
		    else
			file << "jump titleset " << target_titleset_num
			     << " menu entry root; ";
		}

		file <<  "</button>\n";
	    }

	    file <<
		"      </pgc>\n";
	}

	file << "    </menus>\n";

	if (have_real_title)
	{
	    file <<
		"    <titles>\n"
		"      <pgc>\n";

	    file << "        <pre>\n";

	    // Count chapters in the title.
	    unsigned n_chapters = 0;
	    for (vob_list::const_iterator
		     it = titles_[titleset_num - 1].begin(),
		     end = titles_[titleset_num - 1].end();
		 it != end;
		 ++it)
	    {
		// Chapter start times may be specified in the "chapters"
		// attribute as a comma-separated list.  If this is not
		// specified then the beginning of each file starts a new
		// chapter.  Thus the number of chapters in each file is
		// the number of commas in the chapter attribute, plus 1.
		++n_chapters;
		std::size_t pos = 0;
		while ((pos = it->chapters.find(',', pos)) != std::string::npos)
		{
		    ++n_chapters;
		    ++pos;
		}
	    }

	    // Move the chapter number to scratch so the root menu can
	    // distinguish cases 4 and 5.
	    file << "          g0 = g3; g3 = 0;\n";

	    // Copy the latest menu location for use by the post-routine.
	    file << "          g4 = g2;\n";

	    // Jump to the correct chapter.
	    for (unsigned chapter_num = 1;
		 chapter_num <= n_chapters;
		 ++chapter_num)
		file <<
		    "          if (g0 eq " << 1 + chapter_num << ")\n"
		    "            jump chapter " << chapter_num << ";\n";

	    file << "        </pre>\n";

	    for (vob_list::const_iterator
		     it = titles_[titleset_num - 1].begin(),
		     end = titles_[titleset_num - 1].end();
		 it != end;
		 ++it)
	    {
		file << "        <vob file='" << xml_escape(it->file) << "'";
		if (!it->chapters.empty())
		    file << " chapters='" << xml_escape(it->chapters) << "'";
		if (!it->pause.empty())
		    file << " pause='" << xml_escape(it->pause) << "'";
		file << "/>\n";
	    }

	    // If the user has not exited to the menus and then
	    // resumed the title, set the latest menu location to be
	    // the button after the one that linked to this title.
	    // In any case, return to the (root) menu which will
	    // then jump to the correct menu.
	    file <<
		"        <post>\n"
		"          if (g2 eq g4)\n"
		"            g2 = g2 + " << button_mult << ";\n"
		"          call menu;\n"
		"        </post>\n"
		"      </pgc>\n"
		"    </titles>\n";
	}
	else if (titleset_num != 0) // && !have_real_title
	{
	    file << "    <titles><pgc/></titles>\n";
	}

	file << "  </" << outer_element_name << ">\n";
    }

    file << "</dvdauthor>\n";
    file.close();

    {
	const char * argv[] = {
	    "dvdauthor",
	    "-o", output_dir.c_str(),
	    "-x", name.c_str(),
	    0
	};
	int command_result;
	Glib::spawn_sync(".",
			 Glib::ArrayHandle<std::string>(
			     argv, sizeof(argv)/sizeof(argv[0]),
			     Glib::OWNERSHIP_NONE),
			 Glib::SPAWN_SEARCH_PATH
			 | Glib::SPAWN_STDOUT_TO_DEV_NULL,
			 sigc::slot<void>(),
			 0, 0,
			 &command_result);
	if (command_result != 0)
	    throw std::runtime_error("dvdauthor failed");
    }
}