/**************************************************************************** * * ftraster.c * * The FreeType glyph rasterizer (body). * * Copyright (C) 1996-2023 by * David Turner, Robert Wilhelm, and Werner Lemberg. * * This file is part of the FreeType project, and may only be used, * modified, and distributed under the terms of the FreeType project * license, LICENSE.TXT. By continuing to use, modify, or distribute * this file you indicate that you have read the license and * understand and accept it fully. * */ /************************************************************************** * * This file can be compiled without the rest of the FreeType engine, by * defining the STANDALONE_ macro when compiling it. You also need to * put the files `ftimage.h' and `ftmisc.h' into the $(incdir) * directory. Typically, you should do something like * * - copy `src/raster/ftraster.c' (this file) to your current directory * * - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h' to your * current directory * * - compile `ftraster' with the STANDALONE_ macro defined, as in * * cc -c -DSTANDALONE_ ftraster.c * * The renderer can be initialized with a call to * `ft_standard_raster.raster_new'; a bitmap can be generated * with a call to `ft_standard_raster.raster_render'. * * See the comments and documentation in the file `ftimage.h' for more * details on how the raster works. * */ /************************************************************************** * * This is a rewrite of the FreeType 1.x scan-line converter * */ #ifdef STANDALONE_ /* The size in bytes of the render pool used by the scan-line converter */ /* to do all of its work. */ #define FT_RENDER_POOL_SIZE … #define FT_CONFIG_STANDARD_LIBRARY_H … #include <string.h> /* for memset */ #include "ftmisc.h" #include "ftimage.h" #else /* !STANDALONE_ */ #include "ftraster.h" #include <freetype/internal/ftcalc.h> /* for FT_MulDiv and FT_MulDiv_No_Round */ #include <freetype/ftoutln.h> /* for FT_Outline_Get_CBox */ #endif /* !STANDALONE_ */ /************************************************************************** * * A simple technical note on how the raster works * ----------------------------------------------- * * Converting an outline into a bitmap is achieved in several steps: * * 1 - Decomposing the outline into successive `profiles'. Each * profile is simply an array of scanline intersections on a given * dimension. A profile's main attributes are * * o its scanline position boundaries, i.e. `Ymin' and `Ymax' * * o an array of intersection coordinates for each scanline * between `Ymin' and `Ymax' * * o a direction, indicating whether it was built going `up' or * `down', as this is very important for filling rules * * o its drop-out mode * * 2 - Sweeping the target map's scanlines in order to compute segment * `spans' which are then filled. Additionally, this pass * performs drop-out control. * * The outline data is parsed during step 1 only. The profiles are * built from the bottom of the render pool, used as a stack. The * following graphics shows the profile list under construction: * * __________________________________________________________ _ _ * | | | | | * | profile | coordinates for | profile | coordinates for |--> * | 1 | profile 1 | 2 | profile 2 |--> * |_________|_________________|_________|_________________|__ _ _ * * ^ ^ * | | * start of render pool top * * The top of the profile stack is kept in the `top' variable. * * As you can see, a profile record is pushed on top of the render * pool, which is then followed by its coordinates/intersections. If * a change of direction is detected in the outline, a new profile is * generated until the end of the outline. * * Note that when all profiles have been generated, the function * Finalize_Profile_Table() is used to record, for each profile, its * bottom-most scanline as well as the scanline above its upmost * boundary. These positions are called `y-turns' because they (sort * of) correspond to local extrema. They are stored in a sorted list * built from the top of the render pool as a downwards stack: * * _ _ _______________________________________ * | | * <--| sorted list of | * <--| extrema scanlines | * _ _ __________________|____________________| * * ^ ^ * | | * maxBuff sizeBuff = end of pool * * This list is later used during the sweep phase in order to * optimize performance (see technical note on the sweep below). * * Of course, the raster detects whether the two stacks collide and * handles the situation properly. * */ /*************************************************************************/ /*************************************************************************/ /** **/ /** CONFIGURATION MACROS **/ /** **/ /*************************************************************************/ /*************************************************************************/ /*************************************************************************/ /*************************************************************************/ /** **/ /** OTHER MACROS (do not change) **/ /** **/ /*************************************************************************/ /*************************************************************************/ /************************************************************************** * * The macro FT_COMPONENT is used in trace mode. It is an implicit * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log * messages during execution. */ #undef FT_COMPONENT #define FT_COMPONENT … #ifdef STANDALONE_ /* Auxiliary macros for token concatenation. */ #define FT_ERR_XCAT … #define FT_ERR_CAT … /* This macro is used to indicate that a function parameter is unused. */ /* Its purpose is simply to reduce compiler warnings. Note also that */ /* simply defining it as `(void)x' doesn't avoid warnings with certain */ /* ANSI compilers (e.g. LCC). */ #define FT_UNUSED … /* Disable the tracing mechanism for simplicity -- developers can */ /* activate it easily by redefining these macros. */ #ifndef FT_ERROR #define FT_ERROR … #endif #ifndef FT_TRACE #define FT_TRACE … #define FT_TRACE1 … #define FT_TRACE6 … #define FT_TRACE7 … #endif #ifndef FT_THROW #define FT_THROW … #endif #define Raster_Err_Ok … #define Raster_Err_Invalid_Outline … #define Raster_Err_Cannot_Render_Glyph … #define Raster_Err_Invalid_Argument … #define Raster_Err_Raster_Overflow … #define Raster_Err_Raster_Uninitialized … #define Raster_Err_Raster_Negative_Height … #define ft_memset … #define FT_DEFINE_RASTER_FUNCS … #else /* !STANDALONE_ */ #include <freetype/internal/ftobjs.h> #include <freetype/internal/ftdebug.h> /* for FT_TRACE, FT_ERROR, and FT_THROW */ #include "rasterrs.h" #endif /* !STANDALONE_ */ #ifndef FT_MEM_SET #define FT_MEM_SET … #endif #ifndef FT_MEM_ZERO #define FT_MEM_ZERO … #endif #ifndef FT_ZERO #define FT_ZERO … #endif /* FMulDiv means `Fast MulDiv'; it is used in case where `b' is */ /* typically a small value and the result of a*b is known to fit into */ /* 32 bits. */ #define FMulDiv( a, b, c ) … /* On the other hand, SMulDiv means `Slow MulDiv', and is used typically */ /* for clipping computations. It simply uses the FT_MulDiv() function */ /* defined in `ftcalc.h'. */ #define SMulDiv … #define SMulDiv_No_Round … /* The rasterizer is a very general purpose component; please leave */ /* the following redefinitions there (you never know your target */ /* environment). */ #ifndef TRUE #define TRUE … #endif #ifndef FALSE #define FALSE … #endif #ifndef NULL #define NULL … #endif #ifndef SUCCESS #define SUCCESS … #endif #ifndef FAILURE #define FAILURE … #endif #define MaxBezier … /* Setting this constant to more than 32 is a */ /* pure waste of space. */ #define Pixel_Bits … /*************************************************************************/ /*************************************************************************/ /** **/ /** SIMPLE TYPE DECLARATIONS **/ /** **/ /*************************************************************************/ /*************************************************************************/ Int; UInt; Short; PUShort; PLong; ULong; PByte; Bool; PAlignment; TPoint; /* values for the `flags' bit field */ #define Flow_Up … #define Overshoot_Top … #define Overshoot_Bottom … /* States of each line, arc, and profile */ TStates; TProfile; PProfile; struct TProfile_ { … }; TProfileList; PProfileList; #define AlignProfileSize … #undef RAS_ARG #undef RAS_ARGS #undef RAS_VAR #undef RAS_VARS #ifdef FT_STATIC_RASTER #define RAS_ARGS … #define RAS_ARG … #define RAS_VARS … #define RAS_VAR … #define FT_UNUSED_RASTER … #else /* !FT_STATIC_RASTER */ #define RAS_ARGS … #define RAS_ARG … #define RAS_VARS … #define RAS_VAR … #define FT_UNUSED_RASTER … #endif /* !FT_STATIC_RASTER */ black_PWorker; /* prototypes used for sweep function dispatch */ Function_Sweep_Init; Function_Sweep_Span; Function_Sweep_Step; /* NOTE: These operations are only valid on 2's complement processors */ #undef FLOOR #undef CEILING #undef TRUNC #undef SCALED #define FLOOR( x ) … #define CEILING( x ) … #define TRUNC( x ) … #define FRAC( x ) … /* scale and shift grid to pixel centers */ #define SCALED( x ) … #define IS_BOTTOM_OVERSHOOT( x ) … #define IS_TOP_OVERSHOOT( x ) … /* Smart dropout rounding to find which pixel is closer to span ends. */ /* To mimick Windows, symmetric cases break down indepenently of the */ /* precision. */ #define SMART( p, q ) … #if FT_RENDER_POOL_SIZE > 2048 #define FT_MAX_BLACK_POOL … #else #define FT_MAX_BLACK_POOL … #endif /* The most used variables are positioned at the top of the structure. */ /* Thus, their offset can be coded with less opcodes, resulting in a */ /* smaller executable. */ struct black_TWorker_ { … }; black_PRaster; #ifdef FT_STATIC_RASTER static black_TWorker ras; #else /* !FT_STATIC_RASTER */ #define ras … #endif /* !FT_STATIC_RASTER */ /*************************************************************************/ /*************************************************************************/ /** **/ /** PROFILES COMPUTATION **/ /** **/ /*************************************************************************/ /*************************************************************************/ /************************************************************************** * * @Function: * Set_High_Precision * * @Description: * Set precision variables according to param flag. * * @Input: * High :: * Set to True for high precision (typically for ppem < 24), * false otherwise. */ static void Set_High_Precision( RAS_ARGS Int High ) { … } /************************************************************************** * * @Function: * New_Profile * * @Description: * Create a new profile in the render pool. * * @Input: * aState :: * The state/orientation of the new profile. * * overshoot :: * Whether the profile's unrounded start position * differs by at least a half pixel. * * @Return: * SUCCESS on success. FAILURE in case of overflow or of incoherent * profile. */ static Bool New_Profile( RAS_ARGS TStates aState, Bool overshoot ) { … } /************************************************************************** * * @Function: * End_Profile * * @Description: * Finalize the current profile. * * @Input: * overshoot :: * Whether the profile's unrounded end position differs * by at least a half pixel. * * @Return: * SUCCESS on success. FAILURE in case of overflow or incoherency. */ static Bool End_Profile( RAS_ARGS Bool overshoot ) { … } /************************************************************************** * * @Function: * Insert_Y_Turn * * @Description: * Insert a salient into the sorted list placed on top of the render * pool. * * @Input: * New y scanline position. * * @Return: * SUCCESS on success. FAILURE in case of overflow. */ static Bool Insert_Y_Turn( RAS_ARGS Int y ) { … } /************************************************************************** * * @Function: * Finalize_Profile_Table * * @Description: * Adjust all links in the profiles list. * * @Return: * SUCCESS on success. FAILURE in case of overflow. */ static Bool Finalize_Profile_Table( RAS_ARG ) { … } /************************************************************************** * * @Function: * Split_Conic * * @Description: * Subdivide one conic Bezier into two joint sub-arcs in the Bezier * stack. * * @Input: * None (subdivided Bezier is taken from the top of the stack). * * @Note: * This routine is the `beef' of this component. It is _the_ inner * loop that should be optimized to hell to get the best performance. */ static void Split_Conic( TPoint* base ) { … } /************************************************************************** * * @Function: * Split_Cubic * * @Description: * Subdivide a third-order Bezier arc into two joint sub-arcs in the * Bezier stack. * * @Note: * This routine is the `beef' of the component. It is one of _the_ * inner loops that should be optimized like hell to get the best * performance. */ static void Split_Cubic( TPoint* base ) { … } /************************************************************************** * * @Function: * Line_Up * * @Description: * Compute the x-coordinates of an ascending line segment and store * them in the render pool. * * @Input: * x1 :: * The x-coordinate of the segment's start point. * * y1 :: * The y-coordinate of the segment's start point. * * x2 :: * The x-coordinate of the segment's end point. * * y2 :: * The y-coordinate of the segment's end point. * * miny :: * A lower vertical clipping bound value. * * maxy :: * An upper vertical clipping bound value. * * @Return: * SUCCESS on success, FAILURE on render pool overflow. */ static Bool Line_Up( RAS_ARGS Long x1, Long y1, Long x2, Long y2, Long miny, Long maxy ) { … } /************************************************************************** * * @Function: * Line_Down * * @Description: * Compute the x-coordinates of an descending line segment and store * them in the render pool. * * @Input: * x1 :: * The x-coordinate of the segment's start point. * * y1 :: * The y-coordinate of the segment's start point. * * x2 :: * The x-coordinate of the segment's end point. * * y2 :: * The y-coordinate of the segment's end point. * * miny :: * A lower vertical clipping bound value. * * maxy :: * An upper vertical clipping bound value. * * @Return: * SUCCESS on success, FAILURE on render pool overflow. */ static Bool Line_Down( RAS_ARGS Long x1, Long y1, Long x2, Long y2, Long miny, Long maxy ) { … } /* A function type describing the functions used to split Bezier arcs */ TSplitter; /************************************************************************** * * @Function: * Bezier_Up * * @Description: * Compute the x-coordinates of an ascending Bezier arc and store * them in the render pool. * * @Input: * degree :: * The degree of the Bezier arc (either 2 or 3). * * splitter :: * The function to split Bezier arcs. * * miny :: * A lower vertical clipping bound value. * * maxy :: * An upper vertical clipping bound value. * * @Return: * SUCCESS on success, FAILURE on render pool overflow. */ static Bool Bezier_Up( RAS_ARGS Int degree, TPoint* arc, TSplitter splitter, Long miny, Long maxy ) { … } /************************************************************************** * * @Function: * Bezier_Down * * @Description: * Compute the x-coordinates of an descending Bezier arc and store * them in the render pool. * * @Input: * degree :: * The degree of the Bezier arc (either 2 or 3). * * splitter :: * The function to split Bezier arcs. * * miny :: * A lower vertical clipping bound value. * * maxy :: * An upper vertical clipping bound value. * * @Return: * SUCCESS on success, FAILURE on render pool overflow. */ static Bool Bezier_Down( RAS_ARGS Int degree, TPoint* arc, TSplitter splitter, Long miny, Long maxy ) { … } /************************************************************************** * * @Function: * Line_To * * @Description: * Inject a new line segment and adjust the Profiles list. * * @Input: * x :: * The x-coordinate of the segment's end point (its start point * is stored in `lastX'). * * y :: * The y-coordinate of the segment's end point (its start point * is stored in `lastY'). * * @Return: * SUCCESS on success, FAILURE on render pool overflow or incorrect * profile. */ static Bool Line_To( RAS_ARGS Long x, Long y ) { … } /************************************************************************** * * @Function: * Conic_To * * @Description: * Inject a new conic arc and adjust the profile list. * * @Input: * cx :: * The x-coordinate of the arc's new control point. * * cy :: * The y-coordinate of the arc's new control point. * * x :: * The x-coordinate of the arc's end point (its start point is * stored in `lastX'). * * y :: * The y-coordinate of the arc's end point (its start point is * stored in `lastY'). * * @Return: * SUCCESS on success, FAILURE on render pool overflow or incorrect * profile. */ static Bool Conic_To( RAS_ARGS Long cx, Long cy, Long x, Long y ) { … } /************************************************************************** * * @Function: * Cubic_To * * @Description: * Inject a new cubic arc and adjust the profile list. * * @Input: * cx1 :: * The x-coordinate of the arc's first new control point. * * cy1 :: * The y-coordinate of the arc's first new control point. * * cx2 :: * The x-coordinate of the arc's second new control point. * * cy2 :: * The y-coordinate of the arc's second new control point. * * x :: * The x-coordinate of the arc's end point (its start point is * stored in `lastX'). * * y :: * The y-coordinate of the arc's end point (its start point is * stored in `lastY'). * * @Return: * SUCCESS on success, FAILURE on render pool overflow or incorrect * profile. */ static Bool Cubic_To( RAS_ARGS Long cx1, Long cy1, Long cx2, Long cy2, Long x, Long y ) { … } #undef SWAP_ #define SWAP_( x, y ) … /************************************************************************** * * @Function: * Decompose_Curve * * @Description: * Scan the outline arrays in order to emit individual segments and * Beziers by calling Line_To() and Bezier_To(). It handles all * weird cases, like when the first point is off the curve, or when * there are simply no `on' points in the contour! * * @Input: * first :: * The index of the first point in the contour. * * last :: * The index of the last point in the contour. * * flipped :: * If set, flip the direction of the curve. * * @Return: * SUCCESS on success, FAILURE on error. */ static Bool Decompose_Curve( RAS_ARGS Int first, Int last, Int flipped ) { … } /************************************************************************** * * @Function: * Convert_Glyph * * @Description: * Convert a glyph into a series of segments and arcs and make a * profiles list with them. * * @Input: * flipped :: * If set, flip the direction of curve. * * @Return: * SUCCESS on success, FAILURE if any error was encountered during * rendering. */ static Bool Convert_Glyph( RAS_ARGS Int flipped ) { … } /*************************************************************************/ /*************************************************************************/ /** **/ /** SCAN-LINE SWEEPS AND DRAWING **/ /** **/ /*************************************************************************/ /*************************************************************************/ /************************************************************************** * * Init_Linked * * Initializes an empty linked list. */ static void Init_Linked( TProfileList* l ) { … } /************************************************************************** * * InsNew * * Inserts a new profile in a linked list. */ static void InsNew( PProfileList list, PProfile profile ) { … } /************************************************************************** * * DelOld * * Removes an old profile from a linked list. */ static void DelOld( PProfileList list, const PProfile profile ) { … } /************************************************************************** * * Sort * * Sorts a trace list. In 95%, the list is already sorted. We need * an algorithm which is fast in this case. Bubble sort is enough * and simple. */ static void Sort( PProfileList list ) { … } /************************************************************************** * * Vertical Sweep Procedure Set * * These four routines are used during the vertical black/white sweep * phase by the generic Draw_Sweep() function. * */ static void Vertical_Sweep_Init( RAS_ARGS Short min, Short max ) { … } static void Vertical_Sweep_Span( RAS_ARGS Short y, FT_F26Dot6 x1, FT_F26Dot6 x2, PProfile left, PProfile right ) { … } static void Vertical_Sweep_Drop( RAS_ARGS Short y, FT_F26Dot6 x1, FT_F26Dot6 x2, PProfile left, PProfile right ) { … } static void Vertical_Sweep_Step( RAS_ARG ) { … } /************************************************************************ * * Horizontal Sweep Procedure Set * * These four routines are used during the horizontal black/white * sweep phase by the generic Draw_Sweep() function. * */ static void Horizontal_Sweep_Init( RAS_ARGS Short min, Short max ) { … } static void Horizontal_Sweep_Span( RAS_ARGS Short y, FT_F26Dot6 x1, FT_F26Dot6 x2, PProfile left, PProfile right ) { … } static void Horizontal_Sweep_Drop( RAS_ARGS Short y, FT_F26Dot6 x1, FT_F26Dot6 x2, PProfile left, PProfile right ) { … } static void Horizontal_Sweep_Step( RAS_ARG ) { … } /************************************************************************** * * Generic Sweep Drawing routine * */ static Bool Draw_Sweep( RAS_ARG ) { … } #ifdef STANDALONE_ /************************************************************************** * * The following functions should only compile in stand-alone mode, * i.e., when building this component without the rest of FreeType. * */ /************************************************************************** * * @Function: * FT_Outline_Get_CBox * * @Description: * Return an outline's `control box'. The control box encloses all * the outline's points, including Bézier control points. Though it * coincides with the exact bounding box for most glyphs, it can be * slightly larger in some situations (like when rotating an outline * that contains Bézier outside arcs). * * Computing the control box is very fast, while getting the bounding * box can take much more time as it needs to walk over all segments * and arcs in the outline. To get the latter, you can use the * `ftbbox' component, which is dedicated to this single task. * * @Input: * outline :: * A pointer to the source outline descriptor. * * @Output: * acbox :: * The outline's control box. * * @Note: * See @FT_Glyph_Get_CBox for a discussion of tricky fonts. */ static void FT_Outline_Get_CBox( const FT_Outline* outline, FT_BBox *acbox ) { if ( outline && acbox ) { Long xMin, yMin, xMax, yMax; if ( outline->n_points == 0 ) { xMin = 0; yMin = 0; xMax = 0; yMax = 0; } else { FT_Vector* vec = outline->points; FT_Vector* limit = vec + outline->n_points; xMin = xMax = vec->x; yMin = yMax = vec->y; vec++; for ( ; vec < limit; vec++ ) { Long x, y; x = vec->x; if ( x < xMin ) xMin = x; if ( x > xMax ) xMax = x; y = vec->y; if ( y < yMin ) yMin = y; if ( y > yMax ) yMax = y; } } acbox->xMin = xMin; acbox->xMax = xMax; acbox->yMin = yMin; acbox->yMax = yMax; } } #endif /* STANDALONE_ */ /************************************************************************** * * @Function: * Render_Single_Pass * * @Description: * Perform one sweep with sub-banding. * * @Input: * flipped :: * If set, flip the direction of the outline. * * @Return: * Renderer error code. */ static int Render_Single_Pass( RAS_ARGS Bool flipped, Int y_min, Int y_max ) { … } /************************************************************************** * * @Function: * Render_Glyph * * @Description: * Render a glyph in a bitmap. Sub-banding if needed. * * @Return: * FreeType error code. 0 means success. */ static FT_Error Render_Glyph( RAS_ARG ) { … } /**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/ /**** a static object. *****/ #ifdef STANDALONE_ static int ft_black_new( void* memory, FT_Raster *araster ) { static black_TRaster the_raster; FT_UNUSED( memory ); *araster = (FT_Raster)&the_raster; FT_ZERO( &the_raster ); return 0; } static void ft_black_done( FT_Raster raster ) { /* nothing */ FT_UNUSED( raster ); } #else /* !STANDALONE_ */ static int ft_black_new( void* memory_, /* FT_Memory */ FT_Raster *araster_ ) /* black_PRaster */ { … } static void ft_black_done( FT_Raster raster_ ) /* black_PRaster */ { … } #endif /* !STANDALONE_ */ static void ft_black_reset( FT_Raster raster, PByte pool_base, ULong pool_size ) { … } static int ft_black_set_mode( FT_Raster raster, ULong mode, void* args ) { … } static int ft_black_render( FT_Raster raster, const FT_Raster_Params* params ) { … } FT_DEFINE_RASTER_FUNCS( ft_standard_raster, FT_GLYPH_FORMAT_OUTLINE, ft_black_new, /* FT_Raster_New_Func raster_new */ ft_black_reset, /* FT_Raster_Reset_Func raster_reset */ ft_black_set_mode, /* FT_Raster_Set_Mode_Func raster_set_mode */ ft_black_render, /* FT_Raster_Render_Func raster_render */ ft_black_done /* FT_Raster_Done_Func raster_done */ ) /* END */