From owner-freebsd-fs@freebsd.org Wed Nov 30 11:07:00 2016 Return-Path: Delivered-To: freebsd-fs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id A40EBC5D9C2; Wed, 30 Nov 2016 11:07:00 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: from mail-yw0-x232.google.com (mail-yw0-x232.google.com [IPv6:2607:f8b0:4002:c05::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 6A70E17C2; Wed, 30 Nov 2016 11:07:00 +0000 (UTC) (envelope-from m.e.sanliturk@gmail.com) Received: by mail-yw0-x232.google.com with SMTP id t125so154910776ywc.1; Wed, 30 Nov 2016 03:07:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=DR6SJRYF+V2xOwoWuWwZjyrDFYOYZAnJew+JVGCqGVw=; b=w8VtJICER3bjlMtALhS0Cj7OVaeVJ55oH3nKqE9lqP9boZB+sIfjGiWKuC3syuPT0E 0Fh5GCKTsh3CYlD/flR6yaCeQLQ4hYj7og8h3HWcs0T4+eMRUhrtt/KGKTXWIGqDeky2 R1QnS/kKbLrTQA5o6s9RM5IweKj1WqtzJq8MEv5jdHd5vDx63r5A7yP6zSMKwHY1ixhe pg/odCTOy5tulhZHDndbR6siKH2VP9bAXFA1kUzNkcLLB3MS/J7zTzl+nbBJORR2/Of9 Hfes8lj1IW8zAYNpL/75MgVABUvTid+NeGXynwv4PWnJFG2bzocAMvPy5JVA4F6cLg+D cZYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=DR6SJRYF+V2xOwoWuWwZjyrDFYOYZAnJew+JVGCqGVw=; b=Sw6THAEq7FAccFM+OPFsXz1dLRrAzZrNzFhwTbA83SHUJDuVmTG6hGXqRJOAbZypSK 1Kly2uCdGjKJXXnGdkl0/E5G+WLIy9GwIs35VDmFsMwhZE8t0VTHg3gSdIEeBEdOSYbX 8y5WEZVA9XmXXbk5JHD+21U86exHLn4galyjL7Xv+bjP3kWOacMJQZlO9OC6W0G5GS2T G5mR9T29Nt22hJ8uTVVKmViETTK4Vda9f2OIBSXnfu5xQfUIzt9vuYiEd4vD72rfsfay S30aVQGFRnC/5I2Ac2YzjcRl6CHC53cvJxnumMV8jweDrtmsvJFOR2yYBHfuBFqkQgPN fcFw== X-Gm-Message-State: AKaTC01+SZdnHKweUS/jMKRHbJYjbu3D8qCYX9UVKaLB6qFn3BbcH+jRVgO4oV3k15GkKtziffXMF0885AP+vw== X-Received: by 10.129.122.136 with SMTP id v130mr35971366ywc.89.1480504019670; Wed, 30 Nov 2016 03:06:59 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.37.4 with HTTP; Wed, 30 Nov 2016 03:06:59 -0800 (PST) In-Reply-To: <25788.1480501137@segfault.tristatelogic.com> References: <25788.1480501137@segfault.tristatelogic.com> From: Mehmet Erol Sanliturk Date: Wed, 30 Nov 2016 03:06:59 -0800 Message-ID: Subject: Re: Calculating size of a corresponding ISO9660+UDF image? To: "Ronald F. Guilmette" Cc: FreeBSD Questions Mailing List , freebsd-fs@freebsd.org Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 30 Nov 2016 11:07:00 -0000 On Wed, Nov 30, 2016 at 2:18 AM, Ronald F. Guilmette wrote: > > I just got my first BluRay burner & a ton of blank single-sided BD-R > media, so I want to start using these for making backups of most or > all of the stuff I have on hard drives, which is a lot. But efficiently > splitting up all of my stuff into nice neat little <25GB bundles seems > like it might be a bit of tricky problem for two reasons. (See below.) > > (If I can't find anything off-the-shelf that will do this job for me, > then I plan to roll my own, either in Perl or C.) > > The burning itself is no problem. I plan to use Imgburn. It is well > regarded, and it's always worked well for me. > > The real problem is one that I have arguably created for myself... I > never want to have to read multiple burnt optical disks in order to > retrieve a single desired file from my backups. So I never want to > split any individual input file across multiple backup volumes. > > Given that small limitation, I am faced with these two modest technical > problems: > > 1) How to perform "bin packing" to get as many files onto each blank BD-R > disk as possible without exceeding the 25GB limit. (This "bin packing" is > said to be an NP-hard problem, but I'll muddle through this part somehow, > even if I end up having my program just try all possible packings. I wasn't > in a hurry anyway. :-) > > 2) How to calculate exactly how much space in the proposed ISO9660+UDF > image > the files that have so far selected for inclusion will actually occupy. > > Really, it is just this second problem that I care about at the moment. > > So, can anybody tell me the magic formula which, when given a set of > on-harddisk files and directories, will calculate exactly how big that > set of input files/directories will be, once they are all rendered into > a single corresponding ISO9660+UDF image? > > If anybody can tell me how to do this calculation, please proceed. I'd > really rather not have to get down on my hands and knees and spend time > groveling around in the bowels of the FreeBSD optical disk drivers in > order to find this information if I can avoid it. > > I mean it can't be THAT complex, now can it? > > > Regards, > rfg > > > P.S. This whole problem... especially the "bin packing" part... feels like > something that somebody else... or maybe a lot of somebody elses... must > have already solved a long long long time ago, and probably many times. > So maybe I just need to find and resuscitate some of those old solutions. > I mean we've been making backups to finite and predictable length tapes > for at least 50 years now, and I can't be the first guy to have ever said > that I don't want to split files across multiple backup volumes. So > where's > the off-the-shelf open source freeware to solve the bin packing problem > for backup tapes? I'm not proud. I'll just re-use that code, thank you > very much. > _______________________________________________ > > I think you may know the following pages and their linked pages : https://en.wikipedia.org/wiki/Bin_packing_problem ( Bin packing problem ) https://en.wikipedia.org/wiki/Cutting_stock_problem ( Cutting stock problem ) <------------------------------------------- This is more relevant for minimum backup media numbers . https://en.wikipedia.org/wiki/Category:Packing_problems ( Category:Packing problems ) Mehmet Erol Sanliturk