/* Copyright 2012 Mozilla Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

'use strict';

(function(root, factory) {
    if (typeof define === 'function' && define.amd) {
        define('pdfjs/core/function', ['exports', 'pdfjs/shared/util',
            'pdfjs/core/primitives', 'pdfjs/core/ps_parser'], factory);
    } else if (typeof exports !== 'undefined') {
        factory(exports, require('../shared/util.js'), require('./primitives.js'),
            require('./ps_parser.js'));
    } else {
        factory((root.pdfjsCoreFunction = {}), root.pdfjsSharedUtil,
            root.pdfjsCorePrimitives, root.pdfjsCorePsParser);
    }
}(this, function(exports, sharedUtil, corePrimitives, corePsParser) {

    var error = sharedUtil.error;
    var info = sharedUtil.info;
    var isArray = sharedUtil.isArray;
    var isBool = sharedUtil.isBool;
    var isDict = corePrimitives.isDict;
    var isStream = corePrimitives.isStream;
    var PostScriptLexer = corePsParser.PostScriptLexer;
    var PostScriptParser = corePsParser.PostScriptParser;

    var PDFFunction = (function PDFFunctionClosure() {
        var CONSTRUCT_SAMPLED = 0;
        var CONSTRUCT_INTERPOLATED = 2;
        var CONSTRUCT_STICHED = 3;
        var CONSTRUCT_POSTSCRIPT = 4;

        return {
            getSampleArray : function PDFFunction_getSampleArray(size, outputSize, bps,
                                                                 str) {
                var i, ii;
                var length = 1;
                for (i = 0, ii = size.length; i < ii; i++) {
                    length *= size[i];
                }
                length *= outputSize;

                var array = new Array(length);
                var codeSize = 0;
                var codeBuf = 0;
                // 32 is a valid bps so shifting won't work
                var sampleMul = 1.0 / (Math.pow(2.0, bps) - 1);

                var strBytes = str.getBytes((length * bps + 7) / 8);
                var strIdx = 0;
                for (i = 0; i < length; i++) {
                    while (codeSize < bps) {
                        codeBuf <<= 8;
                        codeBuf |= strBytes[strIdx++];
                        codeSize += 8;
                    }
                    codeSize -= bps;
                    array[i] = (codeBuf >> codeSize) * sampleMul;
                    codeBuf &= (1 << codeSize) - 1;
                }
                return array;
            },

            getIR : function PDFFunction_getIR(xref, fn) {
                var dict = fn.dict;
                if (!dict) {
                    dict = fn;
                }

                var types = [this.constructSampled,
                    null,
                    this.constructInterpolated,
                    this.constructStiched,
                    this.constructPostScript];

                var typeNum = dict.get('FunctionType');
                var typeFn = types[typeNum];
                if (!typeFn) {
                    error('Unknown type of function');
                }

                return typeFn.call(this, fn, dict, xref);
            },

            fromIR : function PDFFunction_fromIR(IR) {
                var type = IR[0];
                switch (type) {
                    case CONSTRUCT_SAMPLED:
                        return this.constructSampledFromIR(IR);
                    case CONSTRUCT_INTERPOLATED:
                        return this.constructInterpolatedFromIR(IR);
                    case CONSTRUCT_STICHED:
                        return this.constructStichedFromIR(IR);
                    //case CONSTRUCT_POSTSCRIPT:
                    default:
                        return this.constructPostScriptFromIR(IR);
                }
            },

            parse : function PDFFunction_parse(xref, fn) {
                var IR = this.getIR(xref, fn);
                return this.fromIR(IR);
            },

            parseArray : function PDFFunction_parseArray(xref, fnObj) {
                if (!isArray(fnObj)) {
                    // not an array -- parsing as regular function
                    return this.parse(xref, fnObj);
                }

                var fnArray = [];
                for (var j = 0, jj = fnObj.length; j < jj; j++) {
                    var obj = xref.fetchIfRef(fnObj[j]);
                    fnArray.push(PDFFunction.parse(xref, obj));
                }
                return function(src, srcOffset, dest, destOffset) {
                    for (var i = 0, ii = fnArray.length; i < ii; i++) {
                        fnArray[i](src, srcOffset, dest, destOffset + i);
                    }
                };
            },

            constructSampled : function PDFFunction_constructSampled(str, dict) {
                function toMultiArray(arr) {
                    var inputLength = arr.length;
                    var out = [];
                    var index = 0;
                    for (var i = 0; i < inputLength; i += 2) {
                        out[index] = [arr[i], arr[i + 1]];
                        ++index;
                    }
                    return out;
                }

                var domain = dict.getArray('Domain');
                var range = dict.getArray('Range');

                if (!domain || !range) {
                    error('No domain or range');
                }

                var inputSize = domain.length / 2;
                var outputSize = range.length / 2;

                domain = toMultiArray(domain);
                range = toMultiArray(range);

                var size = dict.get('Size');
                var bps = dict.get('BitsPerSample');
                var order = dict.get('Order') || 1;
                if (order !== 1) {
                    // No description how cubic spline interpolation works in PDF32000:2008
                    // As in poppler, ignoring order, linear interpolation may work as good
                    info('No support for cubic spline interpolation: ' + order);
                }

                var encode = dict.getArray('Encode');
                if (!encode) {
                    encode = [];
                    for (var i = 0; i < inputSize; ++i) {
                        encode.push(0);
                        encode.push(size[i] - 1);
                    }
                }
                encode = toMultiArray(encode);

                var decode = dict.getArray('Decode');
                if (!decode) {
                    decode = range;
                } else {
                    decode = toMultiArray(decode);
                }

                var samples = this.getSampleArray(size, outputSize, bps, str);

                return [
                    CONSTRUCT_SAMPLED, inputSize, domain, encode, decode, samples, size,
                    outputSize, Math.pow(2, bps) - 1, range
                ];
            },

            constructSampledFromIR : function PDFFunction_constructSampledFromIR(IR) {
                // See chapter 3, page 109 of the PDF reference
                function interpolate(x, xmin, xmax, ymin, ymax) {
                    return ymin + ((x - xmin) * ((ymax - ymin) / (xmax - xmin)));
                }

                return function constructSampledFromIRResult(src, srcOffset,
                                                             dest, destOffset) {
                    // See chapter 3, page 110 of the PDF reference.
                    var m = IR[1];
                    var domain = IR[2];
                    var encode = IR[3];
                    var decode = IR[4];
                    var samples = IR[5];
                    var size = IR[6];
                    var n = IR[7];
                    //var mask = IR[8];
                    var range = IR[9];

                    // Building the cube vertices: its part and sample index
                    // http://rjwagner49.com/Mathematics/Interpolation.pdf
                    var cubeVertices = 1 << m;
                    var cubeN = new Float64Array(cubeVertices);
                    var cubeVertex = new Uint32Array(cubeVertices);
                    var i, j;
                    for (j = 0; j < cubeVertices; j++) {
                        cubeN[j] = 1;
                    }

                    var k = n, pos = 1;
                    // Map x_i to y_j for 0 <= i < m using the sampled function.
                    for (i = 0; i < m; ++i) {
                        // x_i' = min(max(x_i, Domain_2i), Domain_2i+1)
                        var domain_2i = domain[i][0];
                        var domain_2i_1 = domain[i][1];
                        var xi = Math.min(Math.max(src[srcOffset + i], domain_2i),
                            domain_2i_1);

                        // e_i = Interpolate(x_i', Domain_2i, Domain_2i+1,
                        //                   Encode_2i, Encode_2i+1)
                        var e = interpolate(xi, domain_2i, domain_2i_1,
                            encode[i][0], encode[i][1]);

                        // e_i' = min(max(e_i, 0), Size_i - 1)
                        var size_i = size[i];
                        e = Math.min(Math.max(e, 0), size_i - 1);

                        // Adjusting the cube: N and vertex sample index
                        var e0 = e < size_i - 1 ? Math.floor(e) : e - 1; // e1 = e0 + 1;
                        var n0 = e0 + 1 - e; // (e1 - e) / (e1 - e0);
                        var n1 = e - e0; // (e - e0) / (e1 - e0);
                        var offset0 = e0 * k;
                        var offset1 = offset0 + k; // e1 * k
                        for (j = 0; j < cubeVertices; j++) {
                            if (j & pos) {
                                cubeN[j] *= n1;
                                cubeVertex[j] += offset1;
                            } else {
                                cubeN[j] *= n0;
                                cubeVertex[j] += offset0;
                            }
                        }

                        k *= size_i;
                        pos <<= 1;
                    }

                    for (j = 0; j < n; ++j) {
                        // Sum all cube vertices' samples portions
                        var rj = 0;
                        for (i = 0; i < cubeVertices; i++) {
                            rj += samples[cubeVertex[i] + j] * cubeN[i];
                        }

                        // r_j' = Interpolate(r_j, 0, 2^BitsPerSample - 1,
                        //                    Decode_2j, Decode_2j+1)
                        rj = interpolate(rj, 0, 1, decode[j][0], decode[j][1]);

                        // y_j = min(max(r_j, range_2j), range_2j+1)
                        dest[destOffset + j] = Math.min(Math.max(rj, range[j][0]),
                            range[j][1]);
                    }
                };
            },

            constructInterpolated : function PDFFunction_constructInterpolated(str,
                                                                               dict) {
                var c0 = dict.getArray('C0') || [0];
                var c1 = dict.getArray('C1') || [1];
                var n = dict.get('N');

                if (!isArray(c0) || !isArray(c1)) {
                    error('Illegal dictionary for interpolated function');
                }

                var length = c0.length;
                var diff = [];
                for (var i = 0; i < length; ++i) {
                    diff.push(c1[i] - c0[i]);
                }

                return [CONSTRUCT_INTERPOLATED, c0, diff, n];
            },

            constructInterpolatedFromIR :
                function PDFFunction_constructInterpolatedFromIR(IR) {
                    var c0 = IR[1];
                    var diff = IR[2];
                    var n = IR[3];

                    var length = diff.length;

                    return function constructInterpolatedFromIRResult(src, srcOffset,
                                                                      dest, destOffset) {
                        var x = n === 1 ? src[srcOffset] : Math.pow(src[srcOffset], n);

                        for (var j = 0; j < length; ++j) {
                            dest[destOffset + j] = c0[j] + (x * diff[j]);
                        }
                    };
                },

            constructStiched : function PDFFunction_constructStiched(fn, dict, xref) {
                var domain = dict.getArray('Domain');

                if (!domain) {
                    error('No domain');
                }

                var inputSize = domain.length / 2;
                if (inputSize !== 1) {
                    error('Bad domain for stiched function');
                }

                var fnRefs = dict.get('Functions');
                var fns = [];
                for (var i = 0, ii = fnRefs.length; i < ii; ++i) {
                    fns.push(PDFFunction.getIR(xref, xref.fetchIfRef(fnRefs[i])));
                }

                var bounds = dict.getArray('Bounds');
                var encode = dict.getArray('Encode');

                return [CONSTRUCT_STICHED, domain, bounds, encode, fns];
            },

            constructStichedFromIR : function PDFFunction_constructStichedFromIR(IR) {
                var domain = IR[1];
                var bounds = IR[2];
                var encode = IR[3];
                var fnsIR = IR[4];
                var fns = [];
                var tmpBuf = new Float32Array(1);

                for (var i = 0, ii = fnsIR.length; i < ii; i++) {
                    fns.push(PDFFunction.fromIR(fnsIR[i]));
                }

                return function constructStichedFromIRResult(src, srcOffset,
                                                             dest, destOffset) {
                    var clip = function constructStichedFromIRClip(v, min, max) {
                        if (v > max) {
                            v = max;
                        } else if (v < min) {
                            v = min;
                        }
                        return v;
                    };

                    // clip to domain
                    var v = clip(src[srcOffset], domain[0], domain[1]);
                    // calulate which bound the value is in
                    for (var i = 0, ii = bounds.length; i < ii; ++i) {
                        if (v < bounds[i]) {
                            break;
                        }
                    }

                    // encode value into domain of function
                    var dmin = domain[0];
                    if (i > 0) {
                        dmin = bounds[i - 1];
                    }
                    var dmax = domain[1];
                    if (i < bounds.length) {
                        dmax = bounds[i];
                    }

                    var rmin = encode[2 * i];
                    var rmax = encode[2 * i + 1];

                    // Prevent the value from becoming NaN as a result
                    // of division by zero (fixes issue6113.pdf).
                    tmpBuf[0] = dmin === dmax ? rmin :
                        rmin + (v - dmin) * (rmax - rmin) / (dmax - dmin);

                    // call the appropriate function
                    fns[i](tmpBuf, 0, dest, destOffset);
                };
            },

            constructPostScript : function PDFFunction_constructPostScript(fn, dict,
                                                                           xref) {
                var domain = dict.getArray('Domain');
                var range = dict.getArray('Range');

                if (!domain) {
                    error('No domain.');
                }

                if (!range) {
                    error('No range.');
                }

                var lexer = new PostScriptLexer(fn);
                var parser = new PostScriptParser(lexer);
                var code = parser.parse();

                return [CONSTRUCT_POSTSCRIPT, domain, range, code];
            },

            constructPostScriptFromIR : function PDFFunction_constructPostScriptFromIR(
                IR) {
                var domain = IR[1];
                var range = IR[2];
                var code = IR[3];

                var compiled = (new PostScriptCompiler()).compile(code, domain, range);
                if (compiled) {
                    // Compiled function consists of simple expressions such as addition,
                    // subtraction, Math.max, and also contains 'var' and 'return'
                    // statements. See the generation in the PostScriptCompiler below.
                    /*jshint -W054 */
                    return new Function('src', 'srcOffset', 'dest', 'destOffset', compiled);
                }

                info('Unable to compile PS function');

                var numOutputs = range.length >> 1;
                var numInputs = domain.length >> 1;
                var evaluator = new PostScriptEvaluator(code);
                // Cache the values for a big speed up, the cache size is limited though
                // since the number of possible values can be huge from a PS function.
                var cache = Object.create(null);
                // The MAX_CACHE_SIZE is set to ~4x the maximum number of distinct values
                // seen in our tests.
                var MAX_CACHE_SIZE = 2048 * 4;
                var cache_available = MAX_CACHE_SIZE;
                var tmpBuf = new Float32Array(numInputs);

                return function constructPostScriptFromIRResult(src, srcOffset,
                                                                dest, destOffset) {
                    var i, value;
                    var key = '';
                    var input = tmpBuf;
                    for (i = 0; i < numInputs; i++) {
                        value = src[srcOffset + i];
                        input[i] = value;
                        key += value + '_';
                    }

                    var cachedValue = cache[key];
                    if (cachedValue !== undefined) {
                        dest.set(cachedValue, destOffset);
                        return;
                    }

                    var output = new Float32Array(numOutputs);
                    var stack = evaluator.execute(input);
                    var stackIndex = stack.length - numOutputs;
                    for (i = 0; i < numOutputs; i++) {
                        value = stack[stackIndex + i];
                        var bound = range[i * 2];
                        if (value < bound) {
                            value = bound;
                        } else {
                            bound = range[i * 2 + 1];
                            if (value > bound) {
                                value = bound;
                            }
                        }
                        output[i] = value;
                    }
                    if (cache_available > 0) {
                        cache_available--;
                        cache[key] = output;
                    }
                    dest.set(output, destOffset);
                };
            }
        };
    })();

    function isPDFFunction(v) {
        var fnDict;
        if (typeof v !== 'object') {
            return false;
        } else if (isDict(v)) {
            fnDict = v;
        } else if (isStream(v)) {
            fnDict = v.dict;
        } else {
            return false;
        }
        return fnDict.has('FunctionType');
    }

    var PostScriptStack = (function PostScriptStackClosure() {
        var MAX_STACK_SIZE = 100;

        function PostScriptStack(initialStack) {
            this.stack = !initialStack ? [] :
                Array.prototype.slice.call(initialStack, 0);
        }

        PostScriptStack.prototype = {
            push  : function PostScriptStack_push(value) {
                if (this.stack.length >= MAX_STACK_SIZE) {
                    error('PostScript function stack overflow.');
                }
                this.stack.push(value);
            },
            pop   : function PostScriptStack_pop() {
                if (this.stack.length <= 0) {
                    error('PostScript function stack underflow.');
                }
                return this.stack.pop();
            },
            copy  : function PostScriptStack_copy(n) {
                if (this.stack.length + n >= MAX_STACK_SIZE) {
                    error('PostScript function stack overflow.');
                }
                var stack = this.stack;
                for (var i = stack.length - n, j = n - 1; j >= 0; j--, i++) {
                    stack.push(stack[i]);
                }
            },
            index : function PostScriptStack_index(n) {
                this.push(this.stack[this.stack.length - n - 1]);
            },
            // rotate the last n stack elements p times
            roll  : function PostScriptStack_roll(n, p) {
                var stack = this.stack;
                var l = stack.length - n;
                var r = stack.length - 1, c = l + (p - Math.floor(p / n) * n), i, j, t;
                for (i = l, j = r; i < j; i++, j--) {
                    t = stack[i];
                    stack[i] = stack[j];
                    stack[j] = t;
                }
                for (i = l, j = c - 1; i < j; i++, j--) {
                    t = stack[i];
                    stack[i] = stack[j];
                    stack[j] = t;
                }
                for (i = c, j = r; i < j; i++, j--) {
                    t = stack[i];
                    stack[i] = stack[j];
                    stack[j] = t;
                }
            }
        };
        return PostScriptStack;
    })();
    var PostScriptEvaluator = (function PostScriptEvaluatorClosure() {
        function PostScriptEvaluator(operators) {
            this.operators = operators;
        }

        PostScriptEvaluator.prototype = {
            execute : function PostScriptEvaluator_execute(initialStack) {
                var stack = new PostScriptStack(initialStack);
                var counter = 0;
                var operators = this.operators;
                var length = operators.length;
                var operator, a, b;
                while (counter < length) {
                    operator = operators[counter++];
                    if (typeof operator === 'number') {
                        // Operator is really an operand and should be pushed to the stack.
                        stack.push(operator);
                        continue;
                    }
                    switch (operator) {
                        // non standard ps operators
                        case 'jz': // jump if false
                            b = stack.pop();
                            a = stack.pop();
                            if (!a) {
                                counter = b;
                            }
                            break;
                        case 'j': // jump
                            a = stack.pop();
                            counter = a;
                            break;

                        // all ps operators in alphabetical order (excluding if/ifelse)
                        case 'abs':
                            a = stack.pop();
                            stack.push(Math.abs(a));
                            break;
                        case 'add':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a + b);
                            break;
                        case 'and':
                            b = stack.pop();
                            a = stack.pop();
                            if (isBool(a) && isBool(b)) {
                                stack.push(a && b);
                            } else {
                                stack.push(a & b);
                            }
                            break;
                        case 'atan':
                            a = stack.pop();
                            stack.push(Math.atan(a));
                            break;
                        case 'bitshift':
                            b = stack.pop();
                            a = stack.pop();
                            if (a > 0) {
                                stack.push(a << b);
                            } else {
                                stack.push(a >> b);
                            }
                            break;
                        case 'ceiling':
                            a = stack.pop();
                            stack.push(Math.ceil(a));
                            break;
                        case 'copy':
                            a = stack.pop();
                            stack.copy(a);
                            break;
                        case 'cos':
                            a = stack.pop();
                            stack.push(Math.cos(a));
                            break;
                        case 'cvi':
                            a = stack.pop() | 0;
                            stack.push(a);
                            break;
                        case 'cvr':
                            // noop
                            break;
                        case 'div':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a / b);
                            break;
                        case 'dup':
                            stack.copy(1);
                            break;
                        case 'eq':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a === b);
                            break;
                        case 'exch':
                            stack.roll(2, 1);
                            break;
                        case 'exp':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(Math.pow(a, b));
                            break;
                        case 'false':
                            stack.push(false);
                            break;
                        case 'floor':
                            a = stack.pop();
                            stack.push(Math.floor(a));
                            break;
                        case 'ge':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a >= b);
                            break;
                        case 'gt':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a > b);
                            break;
                        case 'idiv':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push((a / b) | 0);
                            break;
                        case 'index':
                            a = stack.pop();
                            stack.index(a);
                            break;
                        case 'le':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a <= b);
                            break;
                        case 'ln':
                            a = stack.pop();
                            stack.push(Math.log(a));
                            break;
                        case 'log':
                            a = stack.pop();
                            stack.push(Math.log(a) / Math.LN10);
                            break;
                        case 'lt':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a < b);
                            break;
                        case 'mod':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a % b);
                            break;
                        case 'mul':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a * b);
                            break;
                        case 'ne':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a !== b);
                            break;
                        case 'neg':
                            a = stack.pop();
                            stack.push(-a);
                            break;
                        case 'not':
                            a = stack.pop();
                            if (isBool(a)) {
                                stack.push(!a);
                            } else {
                                stack.push(~a);
                            }
                            break;
                        case 'or':
                            b = stack.pop();
                            a = stack.pop();
                            if (isBool(a) && isBool(b)) {
                                stack.push(a || b);
                            } else {
                                stack.push(a | b);
                            }
                            break;
                        case 'pop':
                            stack.pop();
                            break;
                        case 'roll':
                            b = stack.pop();
                            a = stack.pop();
                            stack.roll(a, b);
                            break;
                        case 'round':
                            a = stack.pop();
                            stack.push(Math.round(a));
                            break;
                        case 'sin':
                            a = stack.pop();
                            stack.push(Math.sin(a));
                            break;
                        case 'sqrt':
                            a = stack.pop();
                            stack.push(Math.sqrt(a));
                            break;
                        case 'sub':
                            b = stack.pop();
                            a = stack.pop();
                            stack.push(a - b);
                            break;
                        case 'true':
                            stack.push(true);
                            break;
                        case 'truncate':
                            a = stack.pop();
                            a = a < 0 ? Math.ceil(a) : Math.floor(a);
                            stack.push(a);
                            break;
                        case 'xor':
                            b = stack.pop();
                            a = stack.pop();
                            if (isBool(a) && isBool(b)) {
                                stack.push(a !== b);
                            } else {
                                stack.push(a ^ b);
                            }
                            break;
                        default:
                            error('Unknown operator ' + operator);
                            break;
                    }
                }
                return stack.stack;
            }
        };
        return PostScriptEvaluator;
    })();

// Most of the PDFs functions consist of simple operations such as:
//   roll, exch, sub, cvr, pop, index, dup, mul, if, gt, add.
//
// We can compile most of such programs, and at the same moment, we can
// optimize some expressions using basic math properties. Keeping track of
// min/max values will allow us to avoid extra Math.min/Math.max calls.
    var PostScriptCompiler = (function PostScriptCompilerClosure() {
        function AstNode(type) {
            this.type = type;
        }

        AstNode.prototype.visit = function(visitor) {
            throw new Error('abstract method');
        };

        function AstArgument(index, min, max) {
            AstNode.call(this, 'args');
            this.index = index;
            this.min = min;
            this.max = max;
        }

        AstArgument.prototype = Object.create(AstNode.prototype);
        AstArgument.prototype.visit = function(visitor) {
            visitor.visitArgument(this);
        };

        function AstLiteral(number) {
            AstNode.call(this, 'literal');
            this.number = number;
            this.min = number;
            this.max = number;
        }

        AstLiteral.prototype = Object.create(AstNode.prototype);
        AstLiteral.prototype.visit = function(visitor) {
            visitor.visitLiteral(this);
        };

        function AstBinaryOperation(op, arg1, arg2, min, max) {
            AstNode.call(this, 'binary');
            this.op = op;
            this.arg1 = arg1;
            this.arg2 = arg2;
            this.min = min;
            this.max = max;
        }

        AstBinaryOperation.prototype = Object.create(AstNode.prototype);
        AstBinaryOperation.prototype.visit = function(visitor) {
            visitor.visitBinaryOperation(this);
        };

        function AstMin(arg, max) {
            AstNode.call(this, 'max');
            this.arg = arg;
            this.min = arg.min;
            this.max = max;
        }

        AstMin.prototype = Object.create(AstNode.prototype);
        AstMin.prototype.visit = function(visitor) {
            visitor.visitMin(this);
        };

        function AstVariable(index, min, max) {
            AstNode.call(this, 'var');
            this.index = index;
            this.min = min;
            this.max = max;
        }

        AstVariable.prototype = Object.create(AstNode.prototype);
        AstVariable.prototype.visit = function(visitor) {
            visitor.visitVariable(this);
        };

        function AstVariableDefinition(variable, arg) {
            AstNode.call(this, 'definition');
            this.variable = variable;
            this.arg = arg;
        }

        AstVariableDefinition.prototype = Object.create(AstNode.prototype);
        AstVariableDefinition.prototype.visit = function(visitor) {
            visitor.visitVariableDefinition(this);
        };

        function ExpressionBuilderVisitor() {
            this.parts = [];
        }

        ExpressionBuilderVisitor.prototype = {
            visitArgument           : function(arg) {
                this.parts.push('Math.max(', arg.min, ', Math.min(',
                    arg.max, ', src[srcOffset + ', arg.index, ']))');
            },
            visitVariable           : function(variable) {
                this.parts.push('v', variable.index);
            },
            visitLiteral            : function(literal) {
                this.parts.push(literal.number);
            },
            visitBinaryOperation    : function(operation) {
                this.parts.push('(');
                operation.arg1.visit(this);
                this.parts.push(' ', operation.op, ' ');
                operation.arg2.visit(this);
                this.parts.push(')');
            },
            visitVariableDefinition : function(definition) {
                this.parts.push('var ');
                definition.variable.visit(this);
                this.parts.push(' = ');
                definition.arg.visit(this);
                this.parts.push(';');
            },
            visitMin                : function(max) {
                this.parts.push('Math.min(');
                max.arg.visit(this);
                this.parts.push(', ', max.max, ')');
            },
            toString                : function() {
                return this.parts.join('');
            }
        };

        function buildAddOperation(num1, num2) {
            if (num2.type === 'literal' && num2.number === 0) {
                // optimization: second operand is 0
                return num1;
            }
            if (num1.type === 'literal' && num1.number === 0) {
                // optimization: first operand is 0
                return num2;
            }
            if (num2.type === 'literal' && num1.type === 'literal') {
                // optimization: operands operand are literals
                return new AstLiteral(num1.number + num2.number);
            }
            return new AstBinaryOperation('+', num1, num2,
                num1.min + num2.min, num1.max + num2.max);
        }

        function buildMulOperation(num1, num2) {
            if (num2.type === 'literal') {
                // optimization: second operands is a literal...
                if (num2.number === 0) {
                    return new AstLiteral(0); // and it's 0
                } else if (num2.number === 1) {
                    return num1; // and it's 1
                } else if (num1.type === 'literal') {
                    // ... and first operands is a literal too
                    return new AstLiteral(num1.number * num2.number);
                }
            }
            if (num1.type === 'literal') {
                // optimization: first operands is a literal...
                if (num1.number === 0) {
                    return new AstLiteral(0); // and it's 0
                } else if (num1.number === 1) {
                    return num2; // and it's 1
                }
            }
            var min = Math.min(num1.min * num2.min, num1.min * num2.max,
                num1.max * num2.min, num1.max * num2.max);
            var max = Math.max(num1.min * num2.min, num1.min * num2.max,
                num1.max * num2.min, num1.max * num2.max);
            return new AstBinaryOperation('*', num1, num2, min, max);
        }

        function buildSubOperation(num1, num2) {
            if (num2.type === 'literal') {
                // optimization: second operands is a literal...
                if (num2.number === 0) {
                    return num1; // ... and it's 0
                } else if (num1.type === 'literal') {
                    // ... and first operands is a literal too
                    return new AstLiteral(num1.number - num2.number);
                }
            }
            if (num2.type === 'binary' && num2.op === '-' &&
                num1.type === 'literal' && num1.number === 1 &&
                num2.arg1.type === 'literal' && num2.arg1.number === 1) {
                // optimization for case: 1 - (1 - x)
                return num2.arg2;
            }
            return new AstBinaryOperation('-', num1, num2,
                num1.min - num2.max, num1.max - num2.min);
        }

        function buildMinOperation(num1, max) {
            if (num1.min >= max) {
                // optimization: num1 min value is not less than required max
                return new AstLiteral(max); // just returning max
            } else if (num1.max <= max) {
                // optimization: num1 max value is not greater than required max
                return num1; // just returning an argument
            }
            return new AstMin(num1, max);
        }

        function PostScriptCompiler() {
        }

        PostScriptCompiler.prototype = {
            compile : function PostScriptCompiler_compile(code, domain, range) {
                var stack = [];
                var i, ii;
                var instructions = [];
                var inputSize = domain.length >> 1, outputSize = range.length >> 1;
                var lastRegister = 0;
                var n, j;
                var num1, num2, ast1, ast2, tmpVar, item;
                for (i = 0; i < inputSize; i++) {
                    stack.push(new AstArgument(i, domain[i * 2], domain[i * 2 + 1]));
                }

                for (i = 0, ii = code.length; i < ii; i++) {
                    item = code[i];
                    if (typeof item === 'number') {
                        stack.push(new AstLiteral(item));
                        continue;
                    }

                    switch (item) {
                        case 'add':
                            if (stack.length < 2) {
                                return null;
                            }
                            num2 = stack.pop();
                            num1 = stack.pop();
                            stack.push(buildAddOperation(num1, num2));
                            break;
                        case 'cvr':
                            if (stack.length < 1) {
                                return null;
                            }
                            break;
                        case 'mul':
                            if (stack.length < 2) {
                                return null;
                            }
                            num2 = stack.pop();
                            num1 = stack.pop();
                            stack.push(buildMulOperation(num1, num2));
                            break;
                        case 'sub':
                            if (stack.length < 2) {
                                return null;
                            }
                            num2 = stack.pop();
                            num1 = stack.pop();
                            stack.push(buildSubOperation(num1, num2));
                            break;
                        case 'exch':
                            if (stack.length < 2) {
                                return null;
                            }
                            ast1 = stack.pop();
                            ast2 = stack.pop();
                            stack.push(ast1, ast2);
                            break;
                        case 'pop':
                            if (stack.length < 1) {
                                return null;
                            }
                            stack.pop();
                            break;
                        case 'index':
                            if (stack.length < 1) {
                                return null;
                            }
                            num1 = stack.pop();
                            if (num1.type !== 'literal') {
                                return null;
                            }
                            n = num1.number;
                            if (n < 0 || (n | 0) !== n || stack.length < n) {
                                return null;
                            }
                            ast1 = stack[stack.length - n - 1];
                            if (ast1.type === 'literal' || ast1.type === 'var') {
                                stack.push(ast1);
                                break;
                            }
                            tmpVar = new AstVariable(lastRegister++, ast1.min, ast1.max);
                            stack[stack.length - n - 1] = tmpVar;
                            stack.push(tmpVar);
                            instructions.push(new AstVariableDefinition(tmpVar, ast1));
                            break;
                        case 'dup':
                            if (stack.length < 1) {
                                return null;
                            }
                            if (typeof code[i + 1] === 'number' && code[i + 2] === 'gt' &&
                                code[i + 3] === i + 7 && code[i + 4] === 'jz' &&
                                code[i + 5] === 'pop' && code[i + 6] === code[i + 1]) {
                                // special case of the commands sequence for the min operation
                                num1 = stack.pop();
                                stack.push(buildMinOperation(num1, code[i + 1]));
                                i += 6;
                                break;
                            }
                            ast1 = stack[stack.length - 1];
                            if (ast1.type === 'literal' || ast1.type === 'var') {
                                // we don't have to save into intermediate variable a literal or
                                // variable.
                                stack.push(ast1);
                                break;
                            }
                            tmpVar = new AstVariable(lastRegister++, ast1.min, ast1.max);
                            stack[stack.length - 1] = tmpVar;
                            stack.push(tmpVar);
                            instructions.push(new AstVariableDefinition(tmpVar, ast1));
                            break;
                        case 'roll':
                            if (stack.length < 2) {
                                return null;
                            }
                            num2 = stack.pop();
                            num1 = stack.pop();
                            if (num2.type !== 'literal' || num1.type !== 'literal') {
                                // both roll operands must be numbers
                                return null;
                            }
                            j = num2.number;
                            n = num1.number;
                            if (n <= 0 || (n | 0) !== n || (j | 0) !== j || stack.length < n) {
                                // ... and integers
                                return null;
                            }
                            j = ((j % n) + n) % n;
                            if (j === 0) {
                                break; // just skipping -- there are nothing to rotate
                            }
                            Array.prototype.push.apply(stack,
                                stack.splice(stack.length - n, n - j));
                            break;
                        default:
                            return null; // unsupported operator
                    }
                }

                if (stack.length !== outputSize) {
                    return null;
                }

                var result = [];
                instructions.forEach(function(instruction) {
                    var statementBuilder = new ExpressionBuilderVisitor();
                    instruction.visit(statementBuilder);
                    result.push(statementBuilder.toString());
                });
                stack.forEach(function(expr, i) {
                    var statementBuilder = new ExpressionBuilderVisitor();
                    expr.visit(statementBuilder);
                    var min = range[i * 2], max = range[i * 2 + 1];
                    var out = [statementBuilder.toString()];
                    if (min > expr.min) {
                        out.unshift('Math.max(', min, ', ');
                        out.push(')');
                    }
                    if (max < expr.max) {
                        out.unshift('Math.min(', max, ', ');
                        out.push(')');
                    }
                    out.unshift('dest[destOffset + ', i, '] = ');
                    out.push(';');
                    result.push(out.join(''));
                });
                return result.join('\n');
            }
        };

        return PostScriptCompiler;
    })();

    exports.isPDFFunction = isPDFFunction;
    exports.PDFFunction = PDFFunction;
    exports.PostScriptEvaluator = PostScriptEvaluator;
    exports.PostScriptCompiler = PostScriptCompiler;
}));
